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
class Solution:
def maxProfit(self, 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 astronomically past any time limit — the constraints demand polynomial, really linear, work.
Approach 2 — Dynamic programming (state machine)
The insight: the exponential tree above only ever distinguishes two situations per day — holding a share or not holding — so collapse it to two running values. Dynamic programming means solving each distinct subproblem once and reusing the answer; here the subproblem is “best profit so far, given my holding state.”
Let cash = best profit ending day i with no share, hold = best profit ending day i while holding a share:
from typing import List
class Solution:
def maxProfit(self, 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)
The insight: 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 you’d do even better keeping only the positive moves. So the optimum is simply the sum of every positive consecutive difference; no schedule can beat it, and this schedule is legal. A greedy algorithm makes the locally best choice at each step and, when an exchange argument like this telescoping one holds, that’s also globally optimal.
from typing import List
class Solution:
def maxProfit(self, 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.