C++-এ কুলডাউন সহ স্টক কেনা-বেচার সর্বোচ্চ লাভ (Best Time to Buy and Sell Stock with Cooldown)

একটি অ্যারে দেওয়া আছে যেখানে i-তম উপাদান হলো i-তম দিনের স্টকের দাম। আমাদের কাজ হল সর্বোচ্চ লাভ বের করা। যেকোনো সংখ্যক ট্রানজ্যাকশন করা যাবে, কিন্তু দুটি নিয়ম মানতে হবে:

একই সময়ে একাধিক ট্রানজ্যাকশন করা যাবে না (পहলে বেচতে হবে, তারপর কেনা যাবে)
স্টক বেচার পর পরের দিন কেনা যাবে না (১ দিন কুলডাউন)

উদাহরণ

ইনপুট: [1,2,3,0,2] → আউটপুট: ৩

ক্রম: [কেনা, বেচা, কুলডাউন, কেনা, বেচা]

ডাইনামিক প্রোগ্রামিং সমাধান

তিনটি স্টেট মেইনটেইন করুন:

endWithSell: ঐ দিনে বেচে শেষ হওয়া সর্বোচ্চ লাভ
endWithBuy: ঐ দিনে কেনে শেষ হওয়া সর্বোচ্চ লাভ
prevSell, prevBuy: গত দিনের মান

C++ প্রোগ্রাম উদাহরণ

#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;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 2, 3, 0, 2};
    cout << ob.maxProfit(v);
    return 0;
}

ইনপুট / আউটপুট

Input: [1,2,3,0,2]
Output: 3