สมมติว่าเรามีอาร์เรย์ที่องค์ประกอบ ith คือราคาของหุ้นที่กำหนดในวันที่ i เราต้องออกแบบอัลกอริทึมเพื่อหากำไรสูงสุด เราอาจทำธุรกรรมได้มากเท่าที่เราต้องการ (ดังนั้น ซื้อหนึ่งหุ้นและขายหุ้นหนึ่งหุ้นหลายๆ ครั้ง) แต่เราต้องปฏิบัติตามกฎเหล่านี้ –
- เราไม่สามารถทำธุรกรรมหลายรายการพร้อมกันได้ (ดังนั้น เราต้องขายหุ้นก่อนที่คุณจะซื้ออีกครั้ง)
- หลังจากที่เราขายหุ้นของเราแล้ว เราไม่สามารถซื้อหุ้นได้ในวันถัดไป (ใจเย็นๆ 1 วัน)
หากอินพุตเป็นเหมือน [1,2,3,0,2] ผลลัพธ์จะเป็น 3 ลำดับก็เหมือน [ซื้อ, ขาย, คูลดาวน์, ซื้อ, ขาย]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- endWithSell :=0, endWithBuy :=-ve infinity, prevBuy :=0 และ prevSell :=0
- สำหรับ i :=0 ถึงขนาดของอาร์เรย์ที่กำหนด
- prevBuy :=endWithBuy
- endWithBuy :=สูงสุดของ endWithBuy และ prevSell – Arr[i]
- prevSell :=endWithSell
- endWithSell :=สูงสุดของ endWithSell และ prevBuy + Arr[i]
- ผลตอบแทน endWithSell
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxProfit(vector<int>& p) {
int endWithSell = 0;
int endWithBuy = INT_MIN;
int prevBuy =0, prevSell = 0;
for(int i =0;i<p.size();i++){
prevBuy = endWithBuy;
endWithBuy = max(endWithBuy,prevSell - p[i]);
prevSell = endWithSell;
endWithSell = max(endWithSell, prevBuy + p[i]);
}
return endWithSell;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,0,2};
cout << (ob.maxProfit(v));
} อินพุต
[1,2,3,0,2]
ผลลัพธ์
3
