Problem 60 · Dynamic Programming

Best Time to Buy and Sell Stock with Cooldown

MediumClassic DSA & systems

01Problem

Given daily prices, maximize profit with unlimited transactions, where after selling you must wait one day before buying again (hold at most one share).

02Key insight

A three-state machine per day: holding, just-sold (cooldown), and resting. Transitions encode the rule; O(1) space.

03Solution

solution.pypython5 lines

def max_profit(prices: list[int]) -> int:
    hold, sold, rest = float("-inf"), 0, 0
    for p in prices:
        hold, sold, rest = max(hold, rest - p), hold + p, max(rest, sold)
    return int(max(sold, rest))

Try it first.

TimeO(n)

SpaceO(1)

tests.py · 4 passing

tests.pypython4 lines

assert max_profit([1,2,3,0,2]) == 3
assert max_profit([1]) == 0
assert max_profit([]) == 0
assert max_profit([5,4,3]) == 0

04Staff-level follow-up

Add transaction fees or a cap of k trades? Extend the state machine: subtract the fee on sell, or index states by trades used (O(n*k)).