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]: The maximum profit you can achieve on day i if you buy a stock on that day.
• sell[i]: The maximum profit you can achieve on day i if you sell a stock on that day.
• rest[i]: The maximum profit you can achieve on day i if you are in a cooldown state (neither buying nor selling).

The base cases are:

• buy[0] = -prices[0] (buying on day 0)
• sell[0] = 0 (can't sell on day 0 without buying first)
• rest[0] = 0 (no profit on day 0)

The recursive relations are:

• buy[i] = max(buy[i-1], rest[i-1] - prices[i]) (Either keep the previous buy state, or transition from rest state by buying)
• sell[i] = max(sell[i-1], buy[i-1] + prices[i]) (Either keep the previous sell state, or transition from buy state by selling)
• rest[i] = max(rest[i-1], sell[i-1]) (Either keep previous rest state, or transition from sell state to cool down)

Finally, the maximum profit will be max(sell[n-1], rest[n-1]) where n is the length of prices. We use rest[n-1] because we could end in a cooldown state with the maximum profit.

Code (Java)

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }

        int n = prices.length;
        int[] buy = new int[n];
        int[] sell = new int[n];
        int[] rest = new int[n];

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

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

        return Math.max(sell[n - 1], rest[n - 1]);
    }
}

Complexity Analysis

• Time Complexity: O(n), where n is the length of the prices array. We iterate through the array once.
• Space Complexity: O(n), due to the buy, sell, and rest arrays. This can be optimized to O(1) by only storing the previous day's values instead of the entire arrays. This optimization is shown below.

Optimized Code (Java) with O(1) Space

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }

        int buy = -prices[0];
        int sell = 0;
        int rest = 0;

        for (int i = 1; i < prices.length; i++) {
            int prevBuy = buy;
            int prevSell = sell;
            int prevRest = rest;

            buy = Math.max(prevBuy, prevRest - prices[i]);
            sell = Math.max(prevSell, prevBuy + prices[i]);
            rest = Math.max(prevRest, prevSell);
        }

        return Math.max(sell, rest);
    }
}

This optimized version achieves the same result with significantly reduced space complexity.