Best Time to Buy and Sell Stock with Cooldown medium

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (buy one and sell one share of the stock multiple times) with the following restrictions:

• After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

Example 1:

Input: prices = [1,2,3,0,2] Output: 3 Explanation: transactions = [buy, sell, cooldown, buy, sell]

Example 2:

Input: prices = [1] Output: 0

Steps and Explanation

This problem can be solved using dynamic programming. We'll maintain three arrays:

• buy[i]: Maximum profit if we buy on day i.
• sell[i]: Maximum profit if we sell on day i.
• cooldown[i]: Maximum profit if we are in cooldown on day i.

The recurrence relations are:

• buy[i] = max(buy[i-1], cooldown[i-1] - prices[i]) We can either hold onto our previous buy or buy today (if we were in cooldown yesterday).
• sell[i] = max(sell[i-1], buy[i-1] + prices[i]) We can either hold onto our previous sell or sell today (if we bought yesterday).
• cooldown[i] = max(cooldown[i-1], sell[i-1]) We can either hold onto our previous cooldown or transition from a sell yesterday.

The base cases are:

• buy[0] = -prices[0] (Buying on day 0)
• sell[0] = 0 (No sell on day 0)
• cooldown[0] = 0 (No cooldown on day 0)

We iterate through the prices array, calculating buy[i], sell[i], and cooldown[i] for each day. The final answer will be max(sell[n-1], cooldown[n-1]) where n is the length of the prices array.

Code (C++)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1) return 0;

        vector<long long> buy(n, 0);
        vector<long long> sell(n, 0);
        vector<long long> cooldown(n, 0);

        buy[0] = -prices[0];
        sell[0] = 0;
        cooldown[0] = 0;

        for (int i = 1; i < n; ++i) {
            buy[i] = max(buy[i - 1], cooldown[i - 1] - prices[i]);
            sell[i] = max(sell[i - 1], buy[i - 1] + prices[i]);
            cooldown[i] = max(cooldown[i - 1], sell[i - 1]);
        }

        return max(sell[n - 1], cooldown[n - 1]);
    }
};

Complexity

• Time Complexity: O(n), where n is the number of days. We iterate through the prices array once.
• Space Complexity: O(n), due to the buy, sell, and cooldown arrays. This can be optimized to O(1) by only storing the previous day's values instead of the entire arrays. This optimization is left as an exercise for the reader.