Recursion & DP Target: 15s
Three-state machine: hold → sell → rest → buy. After selling, must rest one day before buying.
def maxProfit(prices):
hold = -prices[0] # holding stock
sold = 0 # just sold (cooldown next)
rest = 0 # not holding, free to buy
for p in prices[1:]:
hold, sold, rest = (
max(hold, rest - p), # keep or buy
hold + p, # sell
max(rest, sold), # stay or come off cooldown
)
return max(sold, rest)Type it from memory. Go.