Plain-English Restatement: You have a magical time machine and you know the price of a specific stock for the next N days. You can trade it to make money, but there are rules:
You can't hold more than one share at a time. You have to sell your current share before you can buy another.
When you sell, you are forced to take a "cooldown" day off. You cannot buy anything the very next day. Find the maximum possible profit you can make.
Brute Force Approach: At every day, you have a choice. If you hold a stock, you can sell or wait. If you don't hold a stock, you can buy or wait. You could draw out a massive decision tree exploring every valid combination of actions over the N days.
Time Complexity:O(2^n). Each day gives you roughly 2 choices, leading to an exponential number of possible trading sequences.
Why it's wasteful: If you arrive at Day 5 with $10 in your pocket and holding 0 shares, it does not matter whether you made that $10 through one trade or two trades. The brute force approach calculates the future possibilities for Day 5 multiple times. DP collapses all these identical states together.
The second dimension here is not a position — it is which situation you are in.
The cooldown makes today's options depend on what you did yesterday, so a single "best profit so far" number is not enough. You need to know whether you are holding a share, whether you just sold, or whether you are free to act.
A picture to hold in mind. Imagine you are playing a video game character that can only be in one of three stances: "Holding a shield" (HOLD), "Just dropped the shield" (SOLD), or "Walking normally" (REST). You can't just spawn a shield; you have to transition between these stances legally. You want to finish the game with the highest score possible. At any given step, your best score in a specific stance depends entirely on the best scores from the legal stances you could have been in one step prior.
Three states cover everything:
HOLD — you own a share.
SOLD — you sold today, so tomorrow is a cooldown day.
REST — you own nothing and you are free to buy.
And the transitions follow directly from the rules:
buy sellREST ────────→ HOLD ────────────→ SOLD ↑ ↑ (do nothing) │ └──────────────────────────────────┘ cooldown ends
hold — either you were already holding, or you were resting and bought today (paying the price).
sold — you must have been holding, and you sold today (receiving the price). There is no other way to be in SOLD.
rest — either you were already resting, or you sold yesterday and the cooldown has now passed.
That last line is where the cooldown lives. You can only reach REST from SOLD after a full day, which is exactly what "rest reads yesterday's sold" enforces.
class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 hold = -prices[0] # (1) bought on day 0 sold = float('-inf') # impossible before any sale rest = 0 # doing nothing costs nothing for price in prices[1:]: # (2) prev_hold, prev_sold, prev_rest = hold, sold, rest # (3) hold = max(prev_hold, prev_rest - price) # (4) sold = prev_hold + price # (5) rest = max(prev_rest, prev_sold) # (6) return max(sold, rest) # never end holding a share
ts
function maxProfit(prices: number[]): number { if (!prices.length) return 0; let hold = -prices[0], sold = -Infinity, rest = 0; // (1) for (let i = 1; i < prices.length; i++) { // (2) const [pHold, pSold, pRest] = [hold, sold, rest]; // (3) hold = Math.max(pHold, pRest - prices[i]); // (4) sold = pHold + prices[i]; // (5) rest = Math.max(pRest, pSold); // (6) } return Math.max(sold, rest);}
(1) The three starting values, for day 0. Each one is the best profit if you end the day in that state.
hold = -prices[0]: On day 0, if we decide to end the day in the HOLD state, we must have bought the stock, lowering our profit to -prices[0].
sold = float('-inf'): We can't possibly sell on day 0, so this state is impossible. We set it to negative infinity so it's never chosen by a max() comparison.
rest = 0: If we do nothing on day 0, our profit is 0.
(2) The Loop.for price in prices[1:]: starts from day 1 to the end.
(3) Snapshotting.prev_hold, prev_sold, prev_rest = hold, sold, rest. We freeze yesterday's optimal values. If we didn't do this, updating hold first would corrupt the calculation for sold (which relies on yesterday'shold, not today's).
(4) Hold Transition.hold = max(prev_hold, prev_rest - price). You either kept the stock from yesterday (prev_hold), or you were resting yesterday and bought today (prev_rest - price).
(5) Sold Transition.sold = prev_hold + price. You must have been holding yesterday, and you sold it at today's price.
(6) Rest Transition.rest = max(prev_rest, prev_sold). You either were already resting, or you sold yesterday and are now forced to rest.
Snapshot all three before updating any of them. Every transition reads yesterday's values, so updating hold first and then using it to compute sold mixes today and yesterday. This is the bug in this problem, and it produces answers that are close but wrong.
sold starts at negative infinity because you cannot have sold before owning anything. Starting it at 0 would let the first rest = max(rest, sold) wrongly claim a completed sale.
hold starts at -prices[0] — buying costs money, so holding is a negative position until you sell.
Return max(sold, rest), never hold. Ending while still holding a share means money is tied up in an unsold asset, which is never optimal.
Answer max(3, 2) = 3 ✓. Day 3 is the interesting one: rest reached 2 because day 2's sold was 2, and that made buying at 0 give hold = 2 - 0 = wait, prev_rest - price = 1 - 0 = 1. The cooldown from the day-2 sale is what stops rest being 2 on day 3.
When a constraint makes "the best so far" ambiguous, add a dimension for the situation you are in.
This is a state machine DP, and it is the same move as putting the hop count into the state in 4.21.6 Cheapest Flights. The states are the nodes; the transitions are the edges; you are finding the best path through time.
Drawing the state diagram before writing code is the whole method. With the diagram, the three lines write themselves. Without it, you will guess at the transitions.
Time Complexity:O(n). We loop through the prices array exactly once. Inside the loop, we perform a constant O(1) number of additions and maximum comparisons.
Space Complexity:O(1). We do not allocate an array of size N. We only maintain a few integer variables (hold, sold, rest, and their prev_ equivalents) to track the state transitions.
Prices length is 1: Handled perfectly by the early return or the loop just not running. Returns max(sold, rest) which will be 0.
Prices are monotonically decreasing: e.g., [5, 4, 3, 2, 1]. The hold state will update to the lowest negative price, but sold and rest will remain 0 (or negative). max(sold, rest) returns 0 correctly because it's better not to trade at all.
"Why can't you track a single best profit?" The cooldown makes today's options depend on yesterday's action, so the best-so-far number is ambiguous.
"Draw the state machine." Three states, four transitions. Do it before coding.
"Where is the cooldown enforced?" REST reads yesterday's SOLD, so a full day must pass.
"Why snapshot the variables?" Every transition reads yesterday's values.
"Why not return hold?" You would be holding an unsold share.
"What if there were a transaction fee instead?" Two states, subtracting the fee on sale.
One thing to volunteer: say that this is a state machine and that the second dimension is a situation rather than a position. That framing generalises to the whole stock family and to any problem with a "you cannot do X right after Y" rule.
Next:4.24.4 Coin Change II — where the order of two loops decides whether you count combinations or permutations.