LeetEye LeetEye
Medium 2D Dynamic Programming ~5 min

Best Time to Buy and Sell Stock with Cooldown

2d-dp best-time-to-buy-and-sell-stock-with-cooldown

Problem

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).

Examples

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

State machine: track whether you're holding stock or not, and if you just sold.

State machine with 3 states: hold, sold (cooldown), rest. Sold must go to rest. Rest can go to hold. Each day update all states.

How to Approach This Problem

Pattern Recognition: When you see keywords like best time to buy and sell stock with cooldown 2d-dp, think 2D Dynamic Programming.

Step-by-Step Reasoning

1 At any day, you can be in state:
Answer: All of above
Three states capture all situations.
2 If you're holding stock today, tomorrow you can:
Answer: A and B only
Either keep holding or sell. Can't buy more (already holding).
3 If you just sold today, tomorrow you MUST:
Answer: Rest (cooldown)
Cooldown forces you to rest the day after selling.
4 If you're resting (no stock, not in cooldown), tomorrow you can:
Answer: A and B only
Can buy or continue resting. Can't sell (no stock).
5 hold[i] = max(hold[i-1], rest[i-1] - prices[i])\nsold[i] = hold[i-1] + prices[i]\nrest[i] = max(rest[i-1], sold[i-1])\n\nThe pattern is:
Answer: Both
State machine DP where each state has specific transitions.

Solution

def maxProfit(prices: List[int]) -> int:
    if not prices:
        return 0
    
    # State machine: hold, sold, rest
    hold = -prices[0]  # Bought stock
    sold = 0           # Just sold (cooldown next)
    rest = 0           # Resting (can buy)
    
    for i in range(1, len(prices)):
        prev_hold = hold
        hold = max(hold, rest - prices[i])  # Keep or buy
        rest = max(rest, sold)              # Keep resting or cooldown done
        sold = prev_hold + prices[i]        # Sell
    
    return max(sold, rest)

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice 2D Dynamic Programming problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye