Best Time to Buy/Sell with Cooldown

Best Time to Buy and Sell Stock with Cooldown is a classic dynamic-programming problem disguised as a trading question. The trick is to stop thinking about which days to trade and instead track a tiny state machine: each day you are in one of three states, and the answer falls out of how those states feed each other.

The slow way first

The brute-force idea is to try every combination of buy/sell/skip decisions across all days. That branches into an exponential number of choices — far too slow. Even memoizing on (day, do-I-hold-a-share) works but is fiddly because of the cooldown rule.

The question to ask: while standing on one day, what do I actually need to know from yesterday? Only three numbers: the best profit if I currently hold a share, the best if I just sold today, and the best if I am resting. Everything else is noise.

The idea: three states, updated each day

Define three running values, each meaning "the best profit I can have, ending today, in this state":

• hold — I am holding a share today.
• sold — I sold a share today (so tomorrow is a forced cooldown).
• rest — I am idle today and free to buy tomorrow.

Each day they update from yesterday: hold = max(hold, rest - price) (keep holding, or buy from a rested position), sold = hold + price (sell what I held), and rest = max(rest, prev_sold) (stay idle, or roll in yesterday's sale now that the cooldown has passed).

The cooldown is encoded for free: sold never feeds hold directly, only through rest, which lags a day. That one-day gap is the cooldown.

Walk through it

Step through the animation for prices = [1, 2, 3, 0, 2]. The pointer scans each day. Watch the three state boxes: hold stays at -1 while we own a cheap share, sold rises as selling becomes profitable, and rest carries the best banked profit forward. By the last day, max(sold, rest) = 3.

Pseudocode

hold = -infinity        # best profit while holding a share
sold = 0                # best profit having just sold today
rest = 0                # best profit while idle (free to buy)
for each price in prices:
    prev_sold = sold                  # capture before sold is overwritten
    hold = max(hold, rest - price)    # keep holding, or buy from rest
    sold = hold + price               # sell the share we hold
    rest = max(rest, prev_sold)       # stay idle, or finish cooldown
return max(sold, rest)                # never end while still holding

The Python solution

def max_profit(prices):
    hold = float('-inf')
    sold = 0
    rest = 0
    for price in prices:
        prev_sold = sold
        hold = max(hold, rest - price)
        sold = hold + price
        rest = max(rest, prev_sold)
    return max(sold, rest)

• hold starts at negative infinity because you cannot be holding a share before any day.
• prev_sold snapshots sold before the line below overwrites it, so rest uses yesterday's sale — that lag is the cooldown.
• hold = max(hold, rest - price) is the heart: either keep the share, or buy today, which only the rested state is allowed to do.
• sold = hold + price sells the held share at today's price.
• The answer is max(sold, rest), never hold — you would never finish still owning a share.

Complexity

We collapse the whole problem into three numbers that roll forward one day at a time. That gives O(n) time and O(1) space — no array, no recursion stack.

When this pattern shows up

Practice