मान लीजिए हमारे पास एक ऐरे है जिसके लिए 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