Max profit when every sale forces a one-day rest: track three states each day (holding, just sold, resting) and step them forward together.
▼The problem
LeetCode 309 (Medium). prices[i] is the price on day i. Complete as many buy/sell transactions as you like, holding at most one share at a time, but after selling you must wait one day (cooldown) before buying again. Return the maximum profit.
Examples (LeetCode's): [1, 2, 3, 0, 2] → 3 (buy, sell, cooldown, buy, sell: (2 − 1) + (2 − 0)) and [1] → 0.
The solution
def maxProfit(prices):
hold, sold, rest = -prices[0], 0, 0
for p in prices[1:]:
hold, sold, rest = (max(hold, rest - p),
hold + p,
max(rest, sold))
return max(sold, rest)Transcript
Best Time to Buy and Sell Stock with Cooldown. Each day the stock has a price. Trade as often as you like, holding one share at a time. But after you sell, you must rest a day before buying again. Find the most profit.
Prices one, two, three, zero, two give three: buy at one, sell at two, rest, buy at zero, sell at two. A single day gives zero.
The naive way tries every choice on every day. Each day you act or wait, so the paths double: about two to the n.
Better: each evening you're in one of three states. Hold: you own a share. Sold: you just sold, so tomorrow is a cooldown. Rest: no share, free to buy. Keep the best profit for each. Hold stays, or buys from rest, paying the price. Sold comes only from hold, earning the price. Rest stays, or comes from yesterday's sold.
In code, the three start at minus the first price, zero and zero. Each day, update all three at once from yesterday's values. Return the larger of sold and rest.
Let's walk it. Day one: buy, so hold is minus one. Day two: selling gives one. Day three: selling at three gives two, and rest picks up one. Day four, price zero: rest buys, so hold climbs to one. Day five: sell for three. The answer is three.
One pass with constant work per day: order n time. Three numbers: constant space.
Three states, three rules, one day at a time. That's Best Time to Buy and Sell Stock with Cooldown.