สมมติว่าเรามีอาร์เรย์ที่องค์ประกอบที่ i คือราคาของหุ้นที่กำหนดในวันที่ i เราต้องออกแบบอัลกอริทึมเพื่อหากำไรสูงสุด เราอาจทำธุรกรรมได้มากเท่าที่ต้องการ (ซื้อหนึ่งและขายหนึ่งหุ้นหลายครั้ง) แต่เราต้องปฏิบัติตามกฎเหล่านี้ -
- เราอาจไม่ทำธุรกรรมหลายรายการในเวลาเดียวกัน (ต้องขายหุ้นก่อนจะซื้ออีกครั้ง)
- หลังจากเราขายหุ้นของเรา เราไม่สามารถซื้อหุ้นในวันถัดไปได้ (ดังนั้นเย็นตัว 1 วัน)
ถ้าอินพุตเป็น [1,2,3,0,2] ผลลัพธ์จะเป็น 3 ลำดับคือ [buy, sell, cooldown, buy, sell]
ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- endWithSell := 0, endWithBuy := -ve infinity, prevBuy := 0 และ prevSell := 0
- for i := 0 ถึงขนาดของอาร์เรย์ที่กำหนด
- prevBuy := endWithBuy
- endWithBuy := max ของ endWithBuy และ prevSell - Arr[i]
- prevSell := endWithSell
- endWithSell := max ของ endWithSell และ prevBuy + Arr[i]
- return 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
