LeetCode 309: Best Time to Buy and Sell Stock with Cooldown

Problem Restatement

We are given an integer array prices.

prices[i] is the price of a stock on day i.

We may complete as many transactions as we want, but with two restrictions:

1. We cannot hold more than one stock at the same time.
2. After selling a stock, we cannot buy on the next day. That next day is a cooldown day.

Return the maximum profit we can make.

The official constraints are 1 <= prices.length <= 5000 and 0 <= prices[i] <= 1000. The problem is tagged as Array and Dynamic Programming.

Input and Output

Function shape:

def maxProfit(prices: list[int]) -> int:
    ...

Examples

Example 1:

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

Output:

3

One optimal sequence is:

buy, sell, cooldown, buy, sell

This means:

Total profit:

-1 + 2 + 0 + 0 + 2 = 3

Example 2:

prices = [1]

Output:

0

There is only one day, so no sell can happen after a buy.

First Thought: Try Every Choice

On each day, we may have several choices:

A recursive solution can try all valid choices.

But without memoization, the same subproblems repeat many times.

For example, many different action paths may lead to:

day 4, not holding stock

So plain recursion becomes exponential.

We need dynamic programming.

Key Insight

The decision on each day depends only on our current state.

We do not need the full transaction history.

We only need to know the best profit after each day in these states:

These three states encode the cooldown rule.

If we sell today, tomorrow we cannot buy. That state is represented by sold.

If we are in rest, we are free to buy.

State Transitions

For each price p, compute the next states.

Holding stock

At the end of today, we hold stock in one of two ways:

1. We already held stock yesterday.
2. We were resting yesterday and buy today.

new_hold = max(hold, rest - p)

We cannot buy from sold, because that would mean buying immediately after selling yesterday.

Sold today

At the end of today, we are in sold only if we held stock yesterday and sell today.

new_sold = hold + p

Resting

At the end of today, we are resting if:

1. We were already resting yesterday.
2. We sold yesterday and today is the cooldown day.

new_rest = max(rest, sold)

These three transitions enforce all rules.

Algorithm

Initialize:

hold = -infinity
sold = -infinity
rest = 0

Before any day:

For each price:

1. Compute new_hold.
2. Compute new_sold.
3. Compute new_rest.
4. Replace old states with new states.

At the end, return:

max(sold, rest)

We do not return hold, because holding a stock at the end means we spent money on an unsold stock. Selling it would be required to realize profit.

Correctness

For each day, the three DP states represent the best possible profit among all valid action sequences ending in that state.

The initialization is correct because before trading starts, the only possible state is resting with profit 0.

Assume the states are correct after yesterday.

For today:

new_hold is correct because the only ways to end today holding stock are to keep holding from yesterday, or buy today from a resting state. Buying from yesterday’s sold state is forbidden by the cooldown rule.

new_sold is correct because the only way to sell today is to have held stock yesterday.

new_rest is correct because we can rest after already resting, or spend today as the cooldown day after selling yesterday.

These cases cover every valid action and exclude every invalid action. Therefore, the states remain correct after every day.

At the end, the best realized profit must be in sold or rest, because holding a stock means the last buy has not been closed by a sell. Thus max(sold, rest) is the maximum possible profit.

Complexity

Implementation

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        hold = float("-inf")
        sold = float("-inf")
        rest = 0

        for price in prices:
            new_hold = max(hold, rest - price)
            new_sold = hold + price
            new_rest = max(rest, sold)

            hold = new_hold
            sold = new_sold
            rest = new_rest

        return max(sold, rest)

Code Explanation

We start with three states:

hold = float("-inf")
sold = float("-inf")
rest = 0

rest = 0 means we have done nothing and made no profit.

hold and sold are impossible before processing any day, so they start as negative infinity.

For each price:

for price in prices:

Compute the next holding state:

new_hold = max(hold, rest - price)

This means either keep holding, or buy today from a free resting state.

Compute the next sold state:

new_sold = hold + price

This means sell the stock we held before today.

Compute the next rest state:

new_rest = max(rest, sold)

This means either continue resting, or enter cooldown after selling yesterday.

Then update all states together:

hold = new_hold
sold = new_sold
rest = new_rest

Updating together matters. Each new state must be based on yesterday’s states, not partially updated values from today.

Finally:

return max(sold, rest)

This returns the best profit when we finish without holding stock.

Testing

def run_tests():
    s = Solution()

    assert s.maxProfit([1, 2, 3, 0, 2]) == 3
    assert s.maxProfit([1]) == 0
    assert s.maxProfit([1, 2]) == 1
    assert s.maxProfit([2, 1]) == 0
    assert s.maxProfit([1, 2, 3]) == 2
    assert s.maxProfit([6, 1, 6, 4, 3, 0, 2]) == 7
    assert s.maxProfit([0, 0, 0]) == 0

    print("all tests passed")

run_tests()

Test meaning: