Best Time to Buy and Sell Stock with Cooldown

• Define a recursive function, say solve(day, holdingStock), which calculates the maximum profit from a given day with a given holdingStock status.
• The holdingStock boolean indicates whether we currently own a share.
• Base Case: If day goes beyond the array length, no more transactions are possible, so return 0.
• Recursive Step (If holdingStock is false):
  • Option 1 (Buy): Buy the stock at prices[day]. The profit changes by -prices[day], and we transition to a holdingStock state. The recursive call is -prices[day] + solve(day + 1, true).
  • Option 2 (Rest): Do nothing. The profit doesn't change, and we stay in the not holdingStock state. The recursive call is solve(day + 1, false).
  • Return the maximum of the two options.
• Recursive Step (If holdingStock is true):
  • Option 1 (Sell): Sell the stock at prices[day]. The profit changes by +prices[day]. Due to the cooldown, we must skip the next day. The recursive call is prices[day] + solve(day + 2, false).
  • Option 2 (Hold): Do nothing. The profit doesn't change, and we stay in the holdingStock state. The recursive call is solve(day + 1, true).
  • Return the maximum of the two options.
• The initial call to the function would be solve(0, false).

The core idea is to define a function that represents the maximum profit we can get from a certain day onwards, given our current state (whether we hold a stock or not). This function will branch out, exploring all valid actions at each step.

For any given day i, if we don't have a stock, we can either buy one or rest. If we do have a stock, we can either sell it (and enter a cooldown period) or continue to hold it. The function recursively calls itself for each choice and returns the maximum profit found.

1class Solution {2    public int maxProfit(int[] prices) {3        return solve(0, true, prices);4    }5 6    // The 'canBuy' parameter indicates if we are in a state where buying is a possible action.7    private int solve(int day, boolean canBuy, int[] prices) {8        if (day >= prices.length) {9            return 0;10        }11 12        if (canBuy) {13            // We can either buy today or rest.14            int buyProfit = -prices[day] + solve(day + 1, false, prices);15            int restProfit = solve(day + 1, true, prices);16            return Math.max(buyProfit, restProfit);17        } else { // We are holding a stock and can either sell or hold.18            // We can either sell today (and cooldown) or hold.19            int sellProfit = prices[day] + solve(day + 2, true, prices);20            int holdProfit = solve(day + 1, false, prices);21            return Math.max(sellProfit, holdProfit);22        }23    }24}

• Use the same recursive structure as the brute-force approach.
• Create a 2D memoization table, memo[n][2], where n is the number of days and 2 represents the two states (can buy/can sell).
• Initialize the memoization table with a special value (e.g., -1) to indicate that a state has not been computed.
• In the recursive function solve(day, state), first check if memo[day][state] has been computed. If so, return the stored value immediately.
• If not, compute the result using the recursive logic as before.
• Before returning the computed result, store it in memo[day][state] for future use.

We enhance the recursive solution by adding a memoization table, memo, to store the results for each state (day, state). The state can be represented by an integer: 1 for 'can buy' and 0 for 'can sell'.

Before making recursive calls to compute the profit for a state, we check our memo table. If a result already exists, we use it. Otherwise, we perform the computation and save the result in the table. This ensures that each unique subproblem is solved only once.

1import java.util.Arrays;2 3class Solution {4    public int maxProfit(int[] prices) {5        int[][] memo = new int[prices.length][2];6        for (int[] row : memo) {7            Arrays.fill(row, -1);8        }9        // Start in a state where we can buy (state = 1)10        return solve(0, 1, prices, memo);11    }12 13    // state: 1 for 'can buy', 0 for 'can sell/holding'14    private int solve(int day, int state, int[] prices, int[][] memo) {15        if (day >= prices.length) {16            return 0;17        }18        if (memo[day][state] != -1) {19            return memo[day][state];20        }21 22        int profit;23        if (state == 1) { // Can buy24            int buyProfit = -prices[day] + solve(day + 1, 0, prices, memo);25            int restProfit = solve(day + 1, 1, prices, memo);26            profit = Math.max(buyProfit, restProfit);27        } else { // Can sell or hold28            int sellProfit = prices[day] + solve(day + 2, 1, prices, memo);29            int holdProfit = solve(day + 1, 0, prices, memo);30            profit = Math.max(sellProfit, holdProfit);31        }32        33        memo[day][state] = profit;34        return profit;35    }36}

• Define three DP arrays of size n: buy, sell, and rest.
  • buy[i]: Max profit up to day i, ending in a 'bought' or 'holding' state.
  • sell[i]: Max profit up to day i, ending with a 'sell' on day i.
  • rest[i]: Max profit up to day i, ending in a 'rest' or 'cooldown' state.
• Base Case (Day 0):
  • buy[0] = -prices[0]
  • sell[0] = 0
  • rest[0] = 0
• Transitions (Iterate from i = 1 to n-1):
  • buy[i] = max(buy[i-1], rest[i-1] - prices[i]): We either held from yesterday or bought today (after resting yesterday).
  • sell[i] = buy[i-1] + prices[i]: We must have been holding yesterday to sell today.
  • rest[i] = max(rest[i-1], sell[i-1]): We either rested from a previous rest state or are in cooldown after selling yesterday.
• Final Result: The maximum profit on the last day is max(sell[n-1], rest[n-1]), as we cannot end in a 'buy' state (it implies a net loss).

We can solve this problem iteratively by building up the solution from day 0 to day n-1. We maintain three arrays to track the maximum profit at each day for each possible state.

• buy[i]: The maximum profit on day i if our last action was buying or holding.
• sell[i]: The maximum profit on day i if our last action was selling.
• rest[i]: The maximum profit on day i if our last action was resting or being in cooldown.

The value for each state on day i is calculated based on the values of the states on day i-1, representing the transitions in our state machine.

1class Solution {2    public int maxProfit(int[] prices) {3        if (prices == null || prices.length <= 1) {4            return 0;5        }6        int n = prices.length;7        int[] buy = new int[n];8        int[] sell = new int[n];9        int[] rest = new int[n];10 11        buy[0] = -prices[0];12        sell[0] = 0;13        rest[0] = 0;14 15        for (int i = 1; i < n; i++) {16            buy[i] = Math.max(buy[i - 1], rest[i - 1] - prices[i]);17            sell[i] = buy[i - 1] + prices[i];18            rest[i] = Math.max(rest[i - 1], sell[i - 1]);19        }20 21        return Math.max(sell[n - 1], rest[n - 1]);22    }23}

• Initialize three variables to represent the states for day 0:
  • buy = -prices[0]
  • sell = 0
  • rest = 0
• Iterate from day i = 1 to n-1.
• In each iteration, calculate the new state values based on the previous ones. It's crucial to use the values from the previous iteration, so we store one of them in a temporary variable before it gets updated.
  • prev_buy = buy (store the old buy state)
  • buy = max(buy, rest - prices[i])
  • rest = max(rest, sell) (update rest using the old sell)
  • sell = prev_buy + prices[i] (update sell using the old buy)
• After the loop, the maximum profit is max(sell, rest).

We can optimize the space complexity of the previous DP approach from O(n) to O(1). Since buy[i], sell[i], and rest[i] only depend on buy[i-1], sell[i-1], and rest[i-1], we only need to maintain variables for the previous day's states, not the entire arrays.

We use three variables: buy, sell, and rest to hold the maximum profits for the current day being processed. Inside the loop, we calculate the new values for these states based on their values from the previous day. Care must be taken to use the previous day's values in all calculations within a single iteration.

1class Solution {2    public int maxProfit(int[] prices) {3        if (prices == null || prices.length <= 1) {4            return 0;5        }6        7        int buy = -prices[0];8        int sell = 0;9        int rest = 0;10 11        for (int i = 1; i < prices.length; i++) {12            // Store the previous buy state before it's updated13            int prev_buy = buy;14            15            // Update buy state16            buy = Math.max(buy, rest - prices[i]);17            18            // Store previous sell state to update rest19            int prev_sell = sell;20 21            // Update sell state using the original buy value from previous day22            sell = prev_buy + prices[i];23 24            // Update rest state using the original sell value from previous day25            rest = Math.max(rest, prev_sell);26        }27 28        return Math.max(sell, rest);29    }30}