The problem
Given daily stock prices, maximise profit with as many buy/sell trades as you like, but after you sell you must wait one day (cooldown) before buying again. You can hold at most one share.
Input: prices = [1, 2, 3, 0, 2] Output: 3 (buy 1, sell 2, cool down, buy 0, sell 2)
Picture it
Picture a trader who, at the end of every day, is in one of three moods: holding a share, just sold (so must rest tomorrow), or resting (free to buy). Each mood has a number: the best profit possible if you finish the day in that mood. Tomorrow’s numbers come from today’s by following the allowed moves (buy, sell, wait).
How to recognise it
- You make a sequence of decisions day by day (buy, sell, wait) and want the best total.
- A rule links neighbouring days: after selling you must wait one day, and you may hold only one share.
- What you can do today depends only on a small state (holding, just sold, or free), not on the whole history.
- Up to 5000 days rule out trying every combination of actions.
- The profit is a number, so you only need the best value for each state, not the trades themselves.
Start with brute force
Walk through the days. On each day, either do nothing, buy (if you hold nothing), or sell (if you hold a share, then skip the next day).
def max_profit_brute(prices):
n = len(prices)
def go(day, holding): # best profit from this day on
if day >= n:
return 0
best = go(day + 1, holding) # do nothing
if holding:
best = max(best, prices[day] + go(day + 2, False)) # sell, skip a day
else:
best = max(best, -prices[day] + go(day + 1, True)) # buy
return best
return go(0, False)
Each day branches in two ways, so time is about O(2^n) and space O(n) for the recursion. With n = 5000 that is far beyond reach.
From brute force to the idea
- Find the waste.
go(day, holding)has only 2n different inputs, but the recursion computes the same pair again and again. - Name the states. At the end of a day you are in exactly one of three states: hold (own a share), sold (just sold today, so tomorrow is a cooldown) or rest (own nothing and free to buy).
- Store the best profit for each state. Each variable is the best money you can have if you finish today in that state.
- Follow the allowed moves. To hold today, either you already held (
hold) or you bought after resting (rest - p). To be in sold today, you held yesterday and sell at today's pricep:hold + p. To rest today, you rested or finished a cooldown yesterday:max(rest, sold). - Update all three together. The tuple assignment computes the right-hand sides from yesterday's values, so
soldreally uses yesterday'shold. Start withhold = -infbecause you cannot hold a share before day one.
This is the key idea: three numbers describe every possible situation, and each day they are updated from yesterday's values.
The key idea
State machine DP: hold = max(hold, rest − price); sold = hold + price; rest = max(rest, sold). O(n).
Python solution
def max_profit(prices):
hold, sold, rest = -inf, 0, 0
for p in prices:
hold, sold, rest = (max(hold, rest - p), # keep, or buy (only after resting)
hold + p, # sell today
max(rest, sold)) # do nothing (cooldown ends)
return max(sold, rest)LeetCode adds the imports for you. To run this on your own machine, put this at the top: from math import inf
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(2^n): two choices per day without sharing results | O(n): recursion depth |
| State machine (shown code) | O(n): one pass, three updates per day | O(1): only three variables |
Edge cases
- The shown code needs
from math import inf. Without it-infraises aNameError. - Empty list: the loop never runs and the code returns 0.
- One day (
[1]): returns 0, because you cannot sell after buying. - Falling prices (
[5, 4, 3, 2, 1]): returns 0, since doing nothing beats any trade. - Rising prices (
[1, 2, 3, 4, 5]): returns 4, one long hold, which the cooldown cannot improve. - Cooldown matters (
[1, 2, 3, 0, 2]): returns 3. Without the cooldown rule the best is 4, because you could sell on day 3 and buy on the same day.
Common mistakes
- Starting
holdat 0, which pretends you own a free share and overstates profit (see the quiz). - Updating the variables one after another, so
soldsees today's newholdand the cooldown rule is lost. - Returning only
sold, which gives a negative number for falling prices instead of 0. - Allowing a buy right after a sell by using
max(rest, sold) - pfor the buy.
You may trade as often as you like, but every sale costs a fixed fee. There is no cooldown. For prices [1, 3, 2, 8, 4, 9] and fee 2 the answer is 8. Describe your approach, then write it if you like.
Compare with our answer
Two states are enough now: holding a share and holding none. Selling can happen any day, so there is no "just sold" state; the fee is simply taken off at the sale.
from math import inf
def max_profit_fee(prices, fee):
hold, cash = -inf, 0
for p in prices:
hold, cash = (max(hold, cash - p), # keep, or buy
max(cash, hold + p - fee)) # wait, or sell and pay
return cash
For the example this returns 8, and [1, 3, 7, 5, 10, 3] with fee 3 returns 6. An empty list returns 0. Time O(n), space O(1).
A strong answer mentions: dropping the third state because nothing forces a wait, charging the fee once per trade, and returning cash.
1. You may buy and sell as often as you like but can hold at most one share, and every trade costs a fixed fee. Which approach fits best?
The choice each day depends only on whether you hold a share, so two running values give O(n). One buy-sell pair misses multiple trades, and sorting loses the order of days.
2. Why does the shown code compute sold as hold + p using the old hold value?
The single tuple assignment reads yesterday's hold, which is exactly the share you could sell today. Using a freshly updated hold could let a buy and a sell happen on the same day.
3. A learner changes the start to hold, sold, rest = 0, 0, 0. What does max_profit([1, 2, 3, 0, 2]) return?
Starting with hold = 0 pretends a share is owned before day one, so the first sale is pure profit. Running the variant gives 4 instead of 3.
Score 60% or more and the lesson is marked complete.