मान लीजिए कि हमारे पास एक सरणी है जिसके लिए ith तत्व किसी दिए गए स्टॉक की कीमत i दिन है। हमें अधिकतम लाभ ज्ञात करने के लिए एक एल्गोरिथम डिजाइन करना होगा। हम जितने चाहें उतने लेनदेन पूरे कर सकते हैं (इसलिए, एक खरीदें और स्टॉक के एक शेयर को कई बार बेचें)। लेकिन हमें इन नियमों का पालन करना होगा -
- हम एक ही समय में कई लेन-देन नहीं कर सकते हैं (इसलिए, आपके द्वारा दोबारा खरीदने से पहले हमें स्टॉक बेचना चाहिए)।
- अपना स्टॉक बेचने के बाद, हम अगले दिन स्टॉक नहीं खरीद सकते। (तो 1 दिन शांत हो जाओ)
यदि इनपुट [1,2,3,0,2] जैसा है, तो आउटपुट 3 होगा, अनुक्रम [खरीदें, बेचें, ठंडा करें, खरीदें, बेचें]
जैसा हैइसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- endWithSell :=0, endWithBuy :=-ve infinity, prevBuy :=0 और prevSell :=0
- i के लिए:=0 दिए गए सरणी के आकार के लिए
- पिछला खरीदें :=endWithBuy
- endWithBuy :=endWithBuy और prevSell का अधिकतम - Arr[i]
- prevSell :=endWithSell
- endWithSell :=endWithSell और prevBuy + Arr[i] की अधिकतम सीमा
- रिटर्न एंडविथसेल
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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