Stock trading DP
In the stock trading problems, the input is a list of prices, one for each day, and on each day we may buy, sell or wait. To know what we may do next, we need to remember very little about the past, such as whether we own a share right now. Stock trading DP keeps one number for each of these few situations after each day: the largest balance, money received minus money paid, that we can have at that point if we end the day in that situation. The first problem charges a fee on every trade.
prices[i] is the price of one share on day , and every completed trade, a purchase followed by a sale, costs fee. You may hold at most one share at a time, so you must sell before you buy again, and you may make as many trades as you like. Return the largest total profit.
Constraints
-
prices.length -
prices[i] -
fee
Sample 1 · Input
prices = [1,3,2,8,4,9], fee = 2
Output
8
Sample 2 · Input
prices = [1,3,7,5,10,3], fee = 3
Output
6
In the first sample, the best plan buys at 1 and sells at 8, then buys at 4 and sells at 9:
The two plans that come to mind first both earn less. If we treat each rise as its own trade, 1 to 3, 2 to 8 and 4 to 9, we pay three fees and earn . If we make one long trade from 1 to 9, we earn . Both plans are greedy: each follows a fixed rule on the spot, without working out what a trade leaves for the days after it. The best plan joins the first two rises into one trade and keeps the last one apart, and which rises to join depends on the fee. With a fee of 5 on the same prices, the single long trade earns and beats every split.
Trying every plan is far too slow. We call the sequence of actions taken so far a history. Each day we either change position or stay, so days allow up to histories. Here can be 50,000, and is a number with 15,052 digits.
Keep one balance per state
Instead, ask which facts about the past affect what we may do next. Since we may hold at most one share, the only fact about the past that decides tomorrow's legal actions is whether we own one. If we do, we may sell or wait; if we do not, we may buy or wait.
Picture two histories that both end today without a share, one with a balance of 5 and one with a balance of 3. Whatever the second one does from here, the first can do too, and each action changes both balances by the same amount, so the first stays 2 ahead to the end. Two histories that end on the same day, both holding a share or both without one, have the same future, so we can forget the one with the worse balance.
Definition
A state is what we need to know about the past to decide which actions are legal from now on. A transition is one legal action on the next day, such as buying, selling or waiting. It leads from one state to another, or back to the same state when we wait, and changes the balance by the money received or paid.
Our problem has two states. After each day, cash is the best balance among histories that own no share, and hold is the best balance among histories that own one.
What a balance counts
A balance starts at 0, and fees count as money paid. A balance does not include the value of a share we still own, so buying at 1 makes the balance , and it stays there until a sale adds money back. If we draw the states as circles and the transitions as arrows between them, the rules become a small state machine. Each day, the new value of a state is the largest candidate value among the arrows that lead into it.
Buy, sell and wait: the edges between cash and hold
Two arrows lead into each state. Each starts from yesterday’s value of its source state, and the fee is charged once per trade, on the sale.
| Into | From | Move | Candidate value |
|---|---|---|---|
| cash | cash | wait | cash |
| cash | hold | sell | |
| hold | hold | wait | hold |
| hold | cash | buy |
Before day 0 we own nothing and have spent nothing, so cash = 0. No history owns a share yet, so hold starts at , which keeps any sale from coming out of it until a purchase gives it a real value. On a day with price , we compute both new values from the old pair and only then replace both:
The answer is cash after the last day. A history that ends holding a share paid for it and never sold it, so the same history without that last purchase ends with more money.
Apply the edges to the first sample
| Day and price | cash: no share | hold: one share |
|---|---|---|
| Before trading | 0 | impossible |
| Day 0, price 1 | 0 | |
| Day 1, price 3 | 0 | |
| Day 2, price 2 | 0 | |
| Day 3, price 8 | 5 | |
| Day 4, price 4 | 5 | 1 |
| Day 5, price 9 | 8 | 1 |
On day 1, selling the share bought at 1 would give , no better than waiting, so cash stays 0. Buying at 3, or at 2 on day 2, instead of at 1 would only lower the balance, so hold stays . On day 3 the sale finally pays: .
On day 4 that 5 pays for a share at 4, and hold becomes : the first trade's profit has paid for the share, with 1 left over. Selling it on day 5 gives , the sample's answer.
Implement the fee machine
The loop applies the two updates once per day. Both new values come from the old pair before either is stored, so a purchase and a sale on the same day cannot read each other’s results.
def max_profit(prices, fee):
cash, hold = 0, float("-inf")
for price in prices:
cash, hold = (max(cash, hold + price - fee),
max(hold, cash - price))
return cash
print(max_profit([1, 3, 2, 8, 4, 9], 2))
print(max_profit([1, 3, 7, 5, 10, 3], 3))Prints 8 and 6, the two samples' answers.
On the second sample, two trades, 1 to 7 and 5 to 10, would earn , while one trade from 1 to 10 earns . Splitting the trade at 7 avoids the drop from 7 to 5, which is worth 2, but the second trade costs another fee of 3.
The loop does two updates per day, so the largest input takes updates.
Cash and hold invariant
After each day, cash and hold are the best balances of any legal history that ends that day without a share and with one.
Deeper read: why the two maxima are right, and how to recover the trades
Before the first day, the empty history is the only one, with cash = 0 and no share. Now suppose cash and hold are the best balances of the histories that end yesterday in each state. A history that ends today without a share either waited without one or sold the share it held yesterday. A history that ends today with a share either waited with it or bought from yesterday’s cash state.
These cases cover every legal last action. Within each case, every history in the source state could have taken the same last action for the same change in balance, so the best one today extends the best one of that state. The two maxima are therefore exactly the best balances for today.
To recover the buy and sell days themselves, also record which edge gave each maximum, then walk back from cash on the last day. A sell edge means the sale happened that day, and the walk continues from hold on the day before; a buy edge sends it back to cash, and a wait edge keeps it in the same state. The stepper below marks those days.
Step through the fee machine
Each card is a state with its best value so far. When we step a day, each card lists its incoming edges with the kept one in green. After the last day, the chart marks the buy and sell days of one best history. Setting the fee to 5 switches the machine to the single trade from 1 to 9.
Worked example
Trace cash and hold
The trace prints both updates for each day of the second sample. In the preset Falling prices every trade loses and the answer stays 0; in Fee 5: one long trade, on prices 2, 7, 3 and 9, one trade earning 2 beats two that earn 1 between them.
cash means the best profit while holding no share. hold means the best balance while holding one share. Initially, holding is impossible.
- cash
- 0
- hold
- impossible
Change the example input
Current result: 6
With no fee: add every rise
Taking the fee away gives a version with a shorter solution.
prices[i] is the price of one share on day . Each day you may buy, sell or both, as long as you never hold more than one share; you may even sell and buy again on the same day. There is no fee. Return the largest total profit.
Constraints
-
prices.length -
prices[i]
Sample 1 · Input
prices = [7,1,5,3,6,4]
Output
7
Sample 2 · Input
prices = [1,2,3,4,5]
Output
4
Sample 3 · Input
prices = [7,6,4,3,1]
Output
0
We call this problem Stock II. In its first sample, we buy at 1 and sell at 5 for 4, then buy at 3 and sell at 6 for 3, a total of 7. The fee machine with a fee of 0 returns 7. A shorter solution comes from looking at what a single trade earns. Writing for prices[i], holding a share from day to day earns the sum of the daily changes in between:
Holding over a day when the price falls only loses money, and without a fee we can collect every rise on its own, so the answer is the sum of the positive daily changes. This time the greedy plan is the best one. No plan earns more, because a trade earns exactly the daily changes while it holds the share, and with at most one share no daily change is earned twice. In the first sample the rises are 1 to 5 and 3 to 6:
Add up the rises
def max_profit_unlimited(prices):
total = 0
for i in range(1, len(prices)):
total += max(0, prices[i] - prices[i - 1])
return total
print(max_profit_unlimited([7, 1, 5, 3, 6, 4]))
print(max_profit_unlimited([1, 2, 3, 4, 5]))
print(max_profit_unlimited([7, 6, 4, 3, 1]))Prints 7, 4 and 0, the three samples' answers.
The shortcut works only because every rise is free to collect. A fee, a waiting day or a limit on trades breaks it, while the state machine keeps working under each of them.
A cooldown day after each sale
A cooldown breaks the two-state machine, because two histories without a share can now differ in what they may do next.
prices[i] is the price of one share on day . You may make as many trades as you like, holding at most one share at a time, but after you sell you may not buy on the next day. There is no fee. Return the largest total profit.
Constraints
-
prices.length -
prices[i]
Sample 1 · Input
prices = [1,2,3,0,2]
Output
3
Sample 2 · Input
prices = [1]
Output
0
In the first sample, we buy at 1, sell at 2, wait out the cooldown day, buy at 0 and sell at 2, for 3. Selling at 3 on day 2 earns 2 at once, but then day 3, when the price is 0, is the cooldown day, and that history ends with 2.
Of two histories with no share, one that sold today and one that has owned nothing for a week, only the second may buy tomorrow. If we merged them into one cash value, we might keep the first one’s higher balance and then buy with it on a forbidden day. A fact that changes which actions are legal next has to be part of the state, so "no share" splits in two:
- In
cashwe own no share and may buy on the next day. We arrive by waiting there or by waiting out a cooldown. - In
holdwe own one share. We arrive by waiting there or by buying fromcash. - In
coolwe sold today. The only way in is a sale fromhold.
No edge leads from cool to hold, and that missing edge is the cooldown. We start with cash = 0 and with hold and cool at . From yesterday’s values:
The answer is the better of cash and cool after the last day.
cool, and the only edge out of cool goes to cash on the next day, so no purchase can happen on the day after a sale.Three states in code
def max_profit_cooldown(prices):
cash, hold, cool = 0, float("-inf"), float("-inf")
for price in prices:
cash, hold, cool = (max(cash, cool),
max(hold, cash - price),
hold + price)
return max(cash, cool)
print(max_profit_cooldown([1, 2, 3, 0, 2]))
print(max_profit_cooldown([1]))Prints 3 and 0, the two samples' answers.
Step through cash, hold and cooldown
Here is the first sample again. The cash card’s only incoming edges are waiting and leaving the cooldown, and no buy edge leaves cool.
At most two trades, or at most k
A limit on the number of trades also changes what is legal next: after the last allowed trade, we may not buy again.
prices[i] is the price of one share on day . You may complete at most two trades, holding at most one share at a time, with no fee and no cooldown. Return the largest total profit.
Constraints
-
prices.length -
prices[i]
Sample 1 · Input
prices = [3,3,5,0,0,3,1,4]
Output
6
Sample 2 · Input
prices = [1,2,3,4,5]
Output
4
Sample 3 · Input
prices = [7,6,4,3,1]
Output
0
We call this problem Stock III and the next one Stock IV. In the first sample, we buy at 0 and sell at 3, then buy at 1 and sell at 4, for 6. Adding every rise would give , but that takes three trades.
The same task with the limit given as an input: at most k trades.
Constraints
-
k -
prices.length -
prices[i]
Sample 1 · Input
k = 2, prices = [2,4,1]
Output
2
Sample 2 · Input
k = 2, prices = [3,2,6,5,0,3]
Output
7
In the second sample, we buy at 2 and sell at 6, then buy at 0 and sell at 3, for 7.
The number of trades already started becomes part of the state. For each from 1 to , we keep buy[t], the best balance while holding a share with at most trades started, and sell[t], the best balance without a share after at most trades. Buying for trade starts from sell[t - 1], and selling moves buy[t] into sell[t]:
sell[0] stays 0 for doing nothing, and every buy starts impossible.
A chain of 2k + 1 states in code
def max_profit_k(k, prices):
buy = [float("-inf")] * (k + 1)
sell = [0] * (k + 1)
for price in prices:
for t in range(1, k + 1):
buy[t] = max(buy[t], sell[t - 1] - price)
sell[t] = max(sell[t], buy[t] + price)
return sell[k]
print(max_profit_k(2, [3, 3, 5, 0, 0, 3, 1, 4]))
print(max_profit_k(2, [3, 2, 6, 5, 0, 3]))Prints 6 for Stock III's first sample and 7 for Stock IV's second.
Stock III is this loop with . Unlike the fee machine, this loop reads values it updated earlier the same day: sell[t] reads today's buy[t], and buy[t] reads today's sell[t - 1]. Either reading amounts to a purchase and a sale, in one order or the other, at the same price on one day. That earns exactly 0 and only uses up a trade, so it never beats a legal history, and it saves us from keeping copies of the old values. The inner loop runs once for each trade number and day, at most times for Stock IV, and each pass updates two states, buy[t] and sell[t].
Deeper read: when k stops mattering
With unlimited trades, the sum of rises from Stock II is earned by one trade over each run of rising days. Each run spans at least two days and no two runs share a day, so that plan has at most trades. Once , the limit never stops that plan, and the sum of rises gives the answer in without the buy and sell arrays. On a variant with 1,000 days and up to , the loop would take steps, while the sum of rises takes 999.
Count strings with a state machine
A state machine can also count histories instead of keeping the best one.
Count the strings of length made only of the vowels a, e, i, o and u, where an a may only be followed by an e; an e only by an a or an i; an i by any vowel except another i; an o only by an i or a u; and a u only by an a. Return the count modulo .
Constraints
Sample 1 · Input
n = 1
Output
5
Sample 2 · Input
n = 2
Output
10
Sample 3 · Input
n = 5
Output
68
For , the ten strings are ae, ea, ei, ia, ie, io, iu, oi, ou and ua.
Which letter may come next depends only on the last letter of the string, so the state is the last vowel, and five numbers hold how many valid strings of the current length end in each vowel. To find the edges into each state, we read the rules backwards: a can follow e, i or u; e can follow a or i; i can follow e or o; o can follow only i; and u can follow i or o.
Here each history is a string, and different strings in the same state must all be counted, so the counting machine adds its incoming values where the trading machine kept the best one:
For , every count starts at 1, so the new counts for a, e, i, o and u are 3, 2, 2, 1 and 2:
Five counts in code
def count_vowel_permutation(n):
MOD = 10**9 + 7
a = e = i = o = u = 1
for _ in range(n - 1):
a, e, i, o, u = ((e + i + u) % MOD,
(a + i) % MOD,
(e + o) % MOD,
i,
(i + o) % MOD)
return (a + e + i + o + u) % MOD
print(count_vowel_permutation(1))
print(count_vowel_permutation(2))
print(count_vowel_permutation(5))Prints 5, 10 and 68, the three samples' answers.
Every stored count is below , and Python integers do not overflow, so the sums need no care. For , the loop runs 19,999 times.
Time and space of state machines
- Fee and cooldown machines
time - Two or three states, updated once per day.
- Extra space
- Each day reads only the day before.
- At most $k$ trades
time, space buy[t]andsell[t]for each , updated once per day.- Count Vowels Permutation
time, space - Five counts, updated once per letter.
- Trying every history
- Two choices per day.
Common state-machine mistakes
Starting
holdat 0.- Where it breaks
- That is a share we never paid for.
prices = [3]with fee 0 returns3instead of0. - The fix
- Start
holdat minus infinity, or at-prices[0]after day 0.
Charging the fee on the purchase and again on the sale.
- Where it breaks
prices = [1, 5], fee 2 returns instead of .- The fix
- Charge it once per trade, here on the sale.
Updating the cooldown states in place.
- Where it breaks
- Updating
cashfromcooland thenholdfrom the newcashallows a purchase the day after a sale.[1, 2, 3, 0, 2]returns4instead of3. - The fix
- Compute every new value from the old ones first, with a tuple assignment or saved copies.
Blocking a purchase on the sale day instead of the next day.
- Where it breaks
[1, 2, 3, 0, 2]then sells at 3, buys at 0 the next day and returns4instead of3.- The fix
- Only
cashmay buy, andcoolreachescashone day after the sale.
Recall Why can the fee machine forget all but the best balance in each state?
Two histories that end on the same day in the same state have the same legal actions from then on, and each action changes both balances by the same amount, so the worse one stays behind to the end.
Recall With a two-day cooldown after each sale, how many states does the machine need?
Four: hold, cash, cool1 for selling today and cool2 for selling yesterday. A sale leads from hold to cool1, the next day moves cool1 to cool2, the day after moves cool2 to cash, and only cash may buy. Merging cool1 and cool2 would mix a history that may buy in three days with one that may buy in two.
Further reading
- labuladongOne Method to Solve All Stock Problems on LeetCode(opens in a new tab)
One state, made of the day, the trades left and whether you hold a share, applied to all six stock problems.
- cp-algorithmsNumber of paths of fixed length(opens in a new tab)
Counting strings in Count Vowels Permutation is counting walks in a five-state graph; raising its adjacency matrix to a power answers in matrix products.
- Jeff Erickson (PDF)Algorithms, Chapter 3: Dynamic programming(opens in a new tab)
Section 3.5 explains why greedy rules, which decide each step on the spot, so rarely give the best answer, and why dynamic programming is the safer first try. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code.