MediumBlind75ArrayDP

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, but you need to cooldown one day after selling.

Examples

Input
prices = [1,2,3,0,2]
Output
3

Transactions: buy at 1, sell at 2, cooldown, buy at 0, sell at 2. Profit = 1 + 2 = 3.

Input
prices = [1]
Output
0

No transactions can be done.

Constraints

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

Approaches

Recursively try all states: buy, sell, or cooldown.

CodeT: O(2^n) | S: O(n)
def max_profit(prices):
    def helper(i, holding):
        if i >= len(prices):
            return 0
        if holding:
            return max(prices[i] + helper(i + 2, False), helper(i + 1, True))
        else:
            return max(-prices[i] + helper(i + 1, True), helper(i + 1, False))
    return helper(0, False)

Use three states: hold, sold, rest.

CodeT: O(n) | S: O(n)
def max_profit(prices):
    if not prices:
        return 0
    n = len(prices)
    hold = [0] * n
    sold = [0] * n
    rest = [0] * n
    hold[0] = -prices[0]
    for i in range(1, n):
        hold[i] = max(hold[i-1], rest[i-1] - prices[i])
        sold[i] = hold[i-1] + prices[i]
        rest[i] = max(rest[i-1], sold[i-1])
    return max(sold[-1], rest[-1])

Optimize space by only keeping previous values.

Diagram

prices = [1,2,3,0,2] hold=-1, sold=0, rest=0 i=1: hold=max(-1,0-2)=-1, sold=-1+2=1, rest=0 i=2: hold=max(-1,0-3)=-1, sold=-1+3=2, rest=max(0,1)=1 i=3: hold=max(-1,1-0)=1, sold=-1+0=-1, rest=max(1,2)=2 i=4: hold=max(1,2-2)=1, sold=1+2=3, rest=max(2,-1)=2 Result: max(3,2) = 3
CodeT: O(n) | S: O(1)
def max_profit(prices):
    if not prices:
        return 0
    hold = -prices[0]
    sold = 0
    rest = 0
    for i in range(1, len(prices)):
        prev_hold = hold
        prev_sold = sold
        hold = max(prev_hold, rest - prices[i])
        sold = prev_hold + prices[i]
        rest = max(rest, prev_sold)
    return max(sold, rest)

Complexity Comparison

Recursion
T: O(2^n)S: O(n)

Recursively try all states: buy, sell, or cooldown.

DP - State Machine
T: O(n)S: O(n)

Use three states: hold, sold, rest.

Space Optimized State Machine
T: O(n)S: O(1)

Optimize space by only keeping previous values.

Common Mistakes

Not handling the cooldown correctly (must wait one day after selling)

Using a 2D DP when state machine is cleaner

Forgetting that you can hold at most one share

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems