Problem. prices[i] is the price on day i. Choose one day to buy and a later day to sell to maximise profit.
If no profit is possible, return 0.
prices = [7, 1, 5, 3, 6, 4] → 5 (buy at 1 on day 1, sell at 6 on day 4)
prices = [7, 6, 4, 3, 1] → 0 (prices only fall)
ML context. The same scan answers "what's the biggest improvement in a validation metric after its worst point so far?" and, flipped, "what's the largest drop after a peak?", the maximum drawdown, used to watch model quality over time and to measure risk.
This problem is famous because its optimal solution is tiny, and because the follow-ups (change the trading rules) each add exactly one piece of state. That makes it the cleanest example in this module of constraints driving the design.
1. Step 1: Clarify
| Question | Answer | Why it matters |
|---|---|---|
| Must I sell after buying? | Yes, a later day | Rules out pairing a day with itself or the past |
| Can I not trade at all? | Yes, profit 0 | Falling prices return 0, not a negative number |
| How many trades? | One (for now) | The follow-ups change this |
| n? | Up to 10⁵ | O(n²) = 10¹⁰: too slow |
| Empty or one day? | Return 0 | Edge cases |
2. Step 2: Brute force
Try every buy day with every later sell day.
def max_profit_brute(prices):
best = 0
n = len(prices)
for buy in range(n):
for sell in range(buy + 1, n): # sell strictly after buy
best = max(best, prices[sell] - prices[buy])
return best
assert max_profit_brute([7, 1, 5, 3, 6, 4]) == 5
assert max_profit_brute([7, 6, 4, 3, 1]) == 0
assert max_profit_brute([]) == 0 and max_profit_brute([5]) == 0
print("brute force works")
O(n²) time, O(1) space. At n = 10⁵: about 5 × 10⁹ pairs. Too slow, so optimise.
3. Step 3: Optimise: what does the past contribute?
Fix a sell day. Which buy day is best? The cheapest day before it, and nothing else about the past matters. So as we scan forward, keep just one number: the lowest price seen so far. Today's best profit is today's price minus that minimum.
import random
def max_profit(prices):
lowest = float("inf")
best = 0
for p in prices:
lowest = min(lowest, p) # the best buy day so far
best = max(best, p - lowest) # selling today after the best buy
return best
def max_profit_brute(prices):
n = len(prices)
return max((prices[j] - prices[i] for i in range(n) for j in range(i + 1, n)), default=0)
assert max_profit([7, 1, 5, 3, 6, 4]) == 5
rng = random.Random(8)
for _ in range(500):
prices = [rng.randint(1, 30) for _ in range(rng.randint(0, 20))]
assert max_profit(prices) == max(0, max_profit_brute(prices))
print("one pass matches brute force: O(n) time, O(1) space")
- Time: O(n). Space: O(1).
- Order of the two updates: updating
lowestfirst meansp − lowestcan be 0 on the day we buy, never a "sell before buy". That's why it's safe. - This is a dynamic program in disguise: the state "best buy so far" summarises the whole past. Module 12 makes that explicit, and the follow-ups below are exactly that.
Quick check
Why is it enough to remember only the lowest price so far?
Show the answer
B. For any sell day, the best buy day before it is the cheapest one; no other information about the past can improve a sale today — The past matters only through its minimum, so one number replaces the inner loop.
4. The ML mirror: maximum drawdown
Flip the question: the largest drop from a peak to a later low. Same scan, with a running maximum instead of a minimum.
def max_drawdown(values):
peak = float("-inf")
worst = 0.0
for v in values:
peak = max(peak, v) # the highest point so far
worst = max(worst, peak - v) # the deepest fall from it
return worst
accuracy = [0.81, 0.84, 0.86, 0.79, 0.83, 0.88, 0.80]
assert abs(max_drawdown(accuracy) - 0.08) < 1e-9 # 0.88 → 0.80
assert max_drawdown([1, 2, 3]) == 0
print("max drawdown works")
Monitoring a model's accuracy day by day, a drawdown alert ("accuracy fell 8 points below its best") is this exact loop.
5. When the rules change, the state changes
Each new rule asks: what do I need to remember to decide today?
Rule change A: unlimited trades (one share at a time)
Brute force would try every set of non-overlapping trades: exponential.
First principles: any profitable stretch from a low to a high can be split into consecutive daily rises, and capturing every rise earns at least as much as any single longer trade. So the answer is the sum of all positive day-to-day differences.
import random
from functools import lru_cache
def max_profit_unlimited(prices):
return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, len(prices)))
def brute_unlimited(prices):
@lru_cache(maxsize=None)
def best(day, holding): # exhaustive over choices, small inputs only
if day == len(prices):
return 0
skip = best(day + 1, holding)
if holding:
return max(skip, prices[day] + best(day + 1, False)) # sell
return max(skip, -prices[day] + best(day + 1, True)) # buy
return best(0, False)
assert max_profit_unlimited([7, 1, 5, 3, 6, 4]) == 7 # 1→5 and 3→6
rng = random.Random(9)
for _ in range(300):
prices = [rng.randint(1, 20) for _ in range(rng.randint(0, 12))]
assert max_profit_unlimited(prices) == brute_unlimited(prices)
print("sum of rises matches exhaustive search")
O(n) time, O(1) space. Notice the reference solution: a small exhaustive search over "hold or not" states. That search is the general method; the greedy sum is what it simplifies to under this rule.
Rule change B: a fee per trade
Now capturing every small rise loses money to fees, so the greedy sum breaks. Keep two numbers per day: the best profit holding a share and the best profit not holding one.
import random
def max_profit_fee(prices, fee):
cash, hold = 0, float("-inf") # not holding / holding
for p in prices:
cash, hold = max(cash, hold + p - fee), max(hold, cash - p)
return cash
def brute_fee(prices, fee):
from functools import lru_cache
@lru_cache(maxsize=None)
def best(day, holding):
if day == len(prices):
return 0
skip = best(day + 1, holding)
if holding:
return max(skip, prices[day] - fee + best(day + 1, False))
return max(skip, -prices[day] + best(day + 1, True))
return best(0, False)
assert max_profit_fee([1, 3, 2, 8, 4, 9], 2) == 8 # buy 1, sell 8, buy 4, sell 9
rng = random.Random(10)
for _ in range(300):
prices = [rng.randint(1, 20) for _ in range(rng.randint(0, 12))]
fee = rng.randint(0, 5)
assert max_profit_fee(prices, fee) == brute_fee(prices, fee)
print("two-state version matches exhaustive search")
O(n) time, O(1) space: two variables replace the whole search tree.
Rule change C: at most k trades
Now the state needs how many trades remain: for each j ≤ k, the best profit after the j-th buy and after the j-th sell. O(n · k) time, O(k) space.
def max_profit_k(prices, k):
if k == 0 or len(prices) < 2:
return 0
if k >= len(prices) // 2: # enough trades to be 'unlimited'
return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, len(prices)))
buy = [float("-inf")] * (k + 1) # buy[j]: best profit holding after j-th buy
sell = [0] * (k + 1) # sell[j]: best profit after j-th sell
for p in prices:
for j in range(1, k + 1):
buy[j] = max(buy[j], sell[j - 1] - p)
sell[j] = max(sell[j], buy[j] + p)
return sell[k]
assert max_profit_k([3, 2, 6, 5, 0, 3], 2) == 7 # 2→6 and 0→3
assert max_profit_k([7, 1, 5, 3, 6, 4], 1) == 5 # same as the single-trade answer
assert max_profit_k([7, 1, 5, 3, 6, 4], 10) == 7 # same as unlimited
print("k-transaction version works")
The two consistency checks are worth saying: with k = 1 it must equal the single-trade answer, and with large k the unlimited answer. Checking special cases against simpler solutions catches bugs in the general one.
The full table
| Rule | State remembered | Time | Space |
|---|---|---|---|
| One trade | lowest price so far | O(n) | O(1) |
| Unlimited trades | nothing (sum rises) | O(n) | O(1) |
| Unlimited + fee | holding / not holding | O(n) | O(1) |
| Unlimited + one-day cooldown | holding / just sold / resting | O(n) | O(1) |
| At most k trades | best after each of k buys and sells | O(n · k) | O(k) |
| Prices streaming in | lowest so far, best so far | O(1) per price | O(1) |
Quick check
Why does the 'sum every rise' answer fail once each trade costs a fee?
Show the answer
A. Splitting a long rise into many small trades now pays the fee many times, so merging rises into fewer trades can earn more; the decision depends on whether you're holding, which needs state — The greedy argument relied on trades being free. A fee breaks it and brings back a small state machine.
6. Saying it out loud
"Brute force tries every buy and later sell: O(n²). For any sell day, the best buy is the cheapest earlier day, so I keep a running minimum and the best profit: one pass, O(1) space. If trades were unlimited I'd sum every positive daily change; with a fee that greedy breaks, so I'd track holding versus not holding, still O(n). With at most k trades, the state grows to k buy and sell values: O(n·k)."
Check yourself
- Why does a running minimum replace the inner loop?
- Why update
lowestbefore computing today's profit? - How does maximum drawdown relate to this problem, and where is it used in ML?
- Why is summing every positive daily change optimal with unlimited free trades?
- What state does the fee version keep, and why is it needed?
- What two simpler answers should the k-trade version match?
Answers
- For each sell day, the best buy is the cheapest earlier price, so only the minimum of the past matters.
- It makes a same-day "buy and sell" give 0 rather than ever selling before buying.
- It's the mirror: largest fall after a peak, with a running maximum. Used to monitor drops in model metrics over time.
- Any profitable stretch decomposes into consecutive daily rises; capturing all of them earns at least as much as any set of longer trades.
- Best profit while holding and while not holding: whether to sell (paying the fee) depends on that.
- k = 1 equals the single-trade answer; k ≥ n/2 equals the unlimited answer.