{x}
blog image

Best Time to Buy and Sell Stock with Cooldown

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 (i.e., 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).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

 

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

 

Constraints:

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000

309. Best Time to Buy and Sell Stock with Cooldown

This problem asks to find the maximum profit from buying and selling a stock multiple times, with the constraint that after selling, you must wait one day before buying again (cooldown period).

Approach 1: Memoization (Top-Down Dynamic Programming)

This approach uses recursion with memoization to avoid redundant calculations. We define a recursive function dfs(i, j):

  • i: The current day (index in the prices array).
  • j: The state: 0 (not holding stock) or 1 (holding stock).

The base case is when i reaches the end of the prices array, returning 0 profit. Otherwise, we explore two possibilities:

  1. No transaction: dfs(i + 1, j) (continue with the current state)
  2. Transaction:
    • If j == 1 (holding stock): Sell the stock. Profit is prices[i] + dfs(i + 2, 0) (cooldown day).
    • If j == 0 (not holding stock): Buy the stock. Profit is -prices[i] + dfs(i + 1, 1).

We take the maximum of these possibilities. Memoization stores the results of dfs(i, j) to prevent recalculations.

Time Complexity: O(N) due to each state being visited once. Space Complexity: O(N) for the memoization table (can be optimized to O(1) as shown in Approach 3).

Approach 2: Dynamic Programming (Bottom-Up)

This approach iteratively builds a DP table. f[i][j] represents the maximum profit at day i with state j (0 or 1).

  • Initialization: f[0][0] = 0, f[0][1] = -prices[0]
  • Recurrence Relation:
    • f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i]) (No transaction or sell)
    • f[i][1] = max(f[i - 1][1], f[i - 2][0] - prices[i]) (No transaction or buy, considering cooldown)

The final answer is f[n - 1][0].

Time Complexity: O(N) due to iterating through the DP table. Space Complexity: O(N) for the DP table (can be optimized to O(1) as shown in Approach 3).

Approach 3: Optimized Dynamic Programming (Constant Space)

This approach further optimizes Approach 2 by using only three variables to track the necessary states instead of a full DP table:

  • f: Represents f[i][0] (maximum profit without holding stock)
  • f0: Represents f[i-1][0] (previous day's profit without holding stock)
  • f1: Represents f[i][1] (maximum profit holding stock)

The iterative update is as follows:

  1. Update f : f = f0
  2. Update f0: f0 = max(f0, f1 + prices[i])
  3. Update f1: f1 = max(f1, (i > 1 ? f - prices[i] : -prices[i]))

Time Complexity: O(N) Space Complexity: O(1)

Code Examples (Python, Java, C++, Go, TypeScript):

The code examples for all three approaches are provided in the original prompt. Approach 3 is generally preferred for its efficiency. Remember to handle edge cases like empty prices array.