ধরুন আমাদের একটি অ্যারে আছে যার জন্য 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-এর সর্বাধিক - আরার[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
