TL;DR
Greedy: sum every positive day-to-day price increase — O(n) time, O(1) space.
Approach 1 — Brute force
Recurse over every choice: each day, either do nothing, buy (if not holding), or sell (if holding). This explores every legal trade schedule.
from typing import List
def maxProfit(prices: List[int]) -> int:
def best(i: int, holding: bool) -> int:
if i == len(prices):
return 0
skip = best(i + 1, holding)
if holding:
act = prices[i] + best(i + 1, False) # sell today
else:
act = -prices[i] + best(i + 1, True) # buy today
return max(skip, act)
return best(0, False)
Complexity: O(2^n) time, O(n) recursion depth.
At n = 3·10^4, 2^n is far past any time limit. The constraints demand linear work.
Approach 2 — Dynamic programming (state machine)
The recursion only ever distinguishes two situations per day: holding a share or not holding. Collapse it to two running values. Dynamic programming solves each distinct subproblem once and reuses the answer; here the subproblem is “best profit so far, given my holding state.”
Each day you move between the two states:
flowchart LR
Cash["Not holding (cash)"] -->|"buy: - price"| Hold["Holding (hold)"]
Hold -->|"sell: + price"| Cash
Cash -->|"stay out"| Cash
Hold -->|"keep holding"| Hold
Let cash = best profit ending day i with no share, hold = best profit ending day i while holding a share:
from typing import List
def maxProfit(prices: List[int]) -> int:
cash, hold = 0, -prices[0]
for price in prices[1:]:
cash = max(cash, hold + price) # sell today, or stay out
hold = max(hold, cash - price) # buy today, or keep holding
return cash
Walkthrough on prices = [7, 1, 5, 3, 6, 4]:
| day (price) | cash | hold |
|---|
| 7 | 0 | −7 |
| 1 | 0 | −1 |
| 5 | 4 | −1 |
| 3 | 4 | 1 |
| 6 | 7 | 1 |
| 4 | 7 | 3 |
Answer: cash = 7 (end without a share).
Complexity: O(n) time, O(1) space. This state-machine template generalizes to the harder stock problems (cooldowns, transaction fees, at-most-k trades), which is why it’s worth knowing even though this problem has a simpler answer.
Approach 3 — Greedy (sum of positive deltas)
Since you may sell and re-buy the same day, any trade spanning days i→j earns prices[j] - prices[i], which telescopes into the sum of all daily moves in between, and keeping only the positive moves does at least as well. So the optimum is the sum of every positive consecutive difference: no schedule can beat it, and this schedule is legal. A greedy algorithm takes the locally best choice at each step; the telescoping (exchange) argument shows that is also globally optimal here.
from typing import List
def maxProfit(prices: List[int]) -> int:
return sum(
max(b - a, 0)
for a, b in zip(prices, prices[1:])
)
Walkthrough on prices = [7, 1, 5, 3, 6, 4]:
- Daily deltas:
1−7 = −6, 5−1 = +4, 3−5 = −2, 6−3 = +3, 4−6 = −2.
- Keep the positive ones:
4 + 3 = 7.
- That corresponds to real trades — buy at 1 / sell at 5, buy at 3 / sell at 6 — total
7.
On [7, 6, 4, 3, 1] every delta is negative, so the sum is 0: never trade.
Complexity: O(n) time, O(1) space.
Common pitfalls
- Reusing Stock I’s “one trade” logic (max price minus min-so-far) — this variant allows unlimited trades and that answer is too small on
[1, 5, 2, 6] (Stock I: 5, here: 8).
- Trying to explicitly find valleys and peaks with fiddly index bookkeeping — correct but error-prone; the positive-delta sum is the same number with none of the boundary cases.
- Worrying that “sell and buy on the same day” double-counts: the telescoping argument shows chained one-day trades equal one long trade exactly, so no profit is counted twice.
- Returning a negative profit on strictly decreasing input instead of 0 — doing nothing is always an option.
Pattern takeaway
When an allowed operation lets you decompose any plan into unit steps (here: a long trade telescopes into daily trades), compare plans step-by-step — often the greedy “take every profitable unit step” is provably optimal. And when greedy feels hard to trust, the two-state hold/cash DP is the safe, generalizable fallback for the whole stock-problem family.