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 ith day.

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

  • You may not engage in multiple transactions simultaneously (ie, you must sell the stock before you buy again).
  • After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 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 to Solve

  1. State Definition: We'll use dynamic programming. Let's define three arrays:

    • buy[i] : The maximum profit if we buy on day i.
    • sell[i] : The maximum profit if we sell on day i.
    • cooldown[i] : The maximum profit if we are in a cooldown period on day i (meaning we sold on the previous day).

  2. Base Cases:

    • buy[0] = -prices[0] (Buy on day 0)
    • sell[0] = 0 (Cannot sell on day 0 without buying first)
    • cooldown[0] = 0 (No cooldown on day 0)

  3. Recurrence Relation: For each day i (after day 0):

    • buy[i] = max(buy[i-1], cooldown[i-1] - prices[i]) (Either keep the previous buy state or buy today after cooldown)
    • sell[i] = max(sell[i-1], buy[i-1] + prices[i]) (Either keep the previous sell state or sell today)
    • cooldown[i] = max(cooldown[i-1], sell[i-1]) (Either keep the previous cooldown state or enter cooldown after selling)

  4. Result: The maximum profit will be the maximum of sell[n-1] and cooldown[n-1] where n is the length of the prices array.

Explanation

The dynamic programming approach cleverly breaks down the problem into subproblems. Each day, we have three possible states: buying, selling, or cooling down. The recurrence relation ensures we consider the optimal profit from the previous day's state to determine the optimal profit for the current day. The cooldown state is crucial to enforce the constraint of not buying immediately after selling.

Code (TypeScript)

function maxProfitWithCooldown(prices: number[]): number {
    const n = prices.length;
    if (n <= 1) return 0;

    const buy: number[] = new Array(n).fill(0);
    const sell: number[] = new Array(n).fill(0);
    const cooldown: number[] = new Array(n).fill(0);

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


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

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

Complexity

  • 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 cooldown arrays. This could be optimized to O(1) by only storing the values for the current and previous day.