Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Unlimited transactions (buy then sell, repeat) — the maximum profit is simply the sum of every positive day-to-day price increase: profit = Σ max(0, prices[i] − prices[i−1]). Capturing every upward step is provably optimal because any multi-day gain telescopes into consecutive deltas, and skipping the negative ones loses nothing. O(n) time, O(1) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognize that unlimited transactions makes the problem greedy, and whether you can PROVE summing positive deltas is optimal rather than just asserting it.
Where candidates slip
Trying to find the single global min and max (Stock I thinking), or overcomplicating with a transaction-tracking DP when greedy suffices.
How to stand out
Prove the greedy via telescoping (a buy-low/sell-high spanning days equals the sum of the daily deltas in between), then mention the DP state machine as the framework that survives when a transaction limit is added.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewMaximize stock trading profitTransaction limit?UnlimitedAt most kExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
Greedy — Sum of Positive Deltas (Optimal)
1Hint 1Explore hintHide hint
If the price goes up from one day to the next, could you always have profited from that single step by holding across it?
2Hint 2Explore hintHide hint
Any profit from buying on day i and selling on day j > i equals the sum of the consecutive daily changes between them. What does that let you ignore?
3Hint 3Explore hintHide hint
Add prices[i] - prices[i-1] whenever it's positive; skip it otherwise. The total is the maximum profit.
A · Core idea
With unlimited transactions and the ability to rebuy the same day, the problem stops being a search over (buy-day, sell-day) pairs and collapses into a one-line sum. Here is why.
The telescoping identity. Suppose the optimal plan buys on day b and sells on day s (b < s). Its profit is prices[s] − prices[b]. Now rewrite that single span as a sum of consecutive daily steps: prices[s] − prices[b] = (prices[b+1] − prices[b]) + (prices[b+2] − prices[b+1]) + … + (prices[s] − prices[s−1]). The intermediate terms cancel — it telescopes. So holding one share from day b to day s earns exactly the same as making a fresh buy-and-sell on every single day in between (legal, since same-day rebuy is allowed). The two strategies are profit-equivalent.
Why dropping the negative steps is optimal. Once any held span equals the sum of its daily deltas, we're free to decompose the whole timeline into daily decisions: for each day-to-day step we can choose to 'be holding' (earn that delta) or 'be flat' (earn 0). To maximize the total we obviously include a step exactly when its delta is positive and exclude it when it's negative or zero. There is no coupling between days — each step's contribution is independent — so the greedy choice per step is globally optimal. That independence is the crux: with unlimited transactions, a locally good choice can never hurt a future one.
Why this fails the moment transactions are capped. If you may make at most k trades, the steps are no longer independent — spending a transaction on a small up-move might cost you a bigger one later, so you must compare alternatives, which is what DP does. The greedy's correctness rests entirely on 'unlimited', and saying so out loud shows you understand the boundary of the technique.
Geometric reading. Plot the prices as a zig-zag. The greedy sum is the total vertical height of all the rising edges. Buying at every valley and selling at every peak captures exactly those rising edges and none of the falling ones — which is the same number the formula produces.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
prices = [7,1,5,3,6,4]Array state
i=2
5 > 1 → +4
7C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Unlimited transactions + same-day rebuy makes each daily price step an independent yes/no decision worth max(0, delta). Telescoping proves a long hold never beats the sum of its steps, so 'grab every up-step' is optimal — no search needed.
ComplexityO(n) time, O(1) space — A single pass comparing each adjacent pair → O(n) time. Only a running profit accumulator → O(1) space.
E · Edge cases and pitfalls6prices = [5] — Loop never runs (no i=1) → profit 0.Explore edge casesHide edge cases
Edge cases handled
prices = [5]Loop never runs (no i=1) → profit 0.prices = [1,2,3,4,5]Every delta positive → 1+1+1+1 = 4.prices = [3,3,3]All deltas zero → strict > excludes them → profit 0.
Pitfalls
- Using >= instead of > — adds zero-deltas harmlessly but signals fuzzy reasoning; keep it strict.
- Looking for a single global min/max (Stock I mindset) — undercounts multi-swing profit.
- Assuming you can't rebuy the same day — you can, which is why per-step capture is valid.
Approach 2 of 2
DP State Machine — Hold vs Cash
1Hint 1Explore hintHide hint
Track two running states each day: the best profit while holding a share, and the best profit while holding cash (no share).
2Hint 2Explore hintHide hint
Transitions: cash today = max(stay in cash, sell the share we held); hold today = max(keep holding, buy with our cash).
3Hint 3Explore hintHide hint
Because transactions are unlimited, buying simply spends the current cash balance — no transaction counter needed. Answer is the final cash state.
A · Core idea
The DP view models each day as a tiny state machine with two states — cash (no share held) and hold (one share held) — and asks for the best achievable profit in each.
The two transitions. On day i with price p:
cash = max(cash, hold + p)— either we stay in cash, or we sell the share we were holding, addingpto whatever profitholdrepresented.hold = max(hold, cashPrev − p)— either we keep holding, or we buy today, spendingpout of yesterday's cash.
The subtle correctness point is ordering: when updating hold, we want yesterday's cash, not the cash we may have just updated this same day. In the unlimited case it turns out updating cash first and then hold still yields the right answer (selling then rebuying the same day is allowed and is profit-neutral when p cancels), but the clean mental model is to compute both from the previous day's values.
Why this reduces to the greedy here. With unlimited transactions there's no transaction counter to track, so the state space stays at two scalars. Expanding the recurrence, cash ends up accumulating exactly the positive deltas — the DP and the greedy compute the same number. The DP just arrives at it through a more general lens.
Why bother with the heavier method. The DP framework is the one that keeps working when the problem grows teeth: add a per-transaction fee and the sell transition becomes hold + p − fee; add a cooldown and you introduce a third state; cap transactions at k and you add a dimension. The greedy can't bend that way. Presenting the DP signals you can solve the whole Stock I–IV / 309 / 714 family from one template, which is exactly what a follow-up will probe.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
prices = [7,1,5,3,6,4]day0 (7)
hold = max(-inf, -7) = -7
cash=0, hold=-77 (final cash)C · Code with teaching comments
Reference implementation previewpublic int maxProfit(int[] prices) { int cash = 0; int hold = Integer.MIN_VALUE; for (int p : prices) { int prevCash = cash;Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Model trading as a two-state machine (cash/hold) and write the max-profit transitions. It collapses to the greedy when transactions are unlimited, but unlike the greedy it extends to fees, cooldowns, and transaction caps — making it the reusable backbone of every stock problem.
ComplexityO(n) time, O(1) space — Two O(1) state updates per day across one pass → O(n) time. Two scalars carried forward → O(1) space.
E · Edge cases and pitfalls5prices = [2] — One day: hold = -2, cash stays 0 → return 0.Explore edge casesHide edge cases
Edge cases handled
prices = [2]One day: hold = -2, cash stays 0 → return 0.prices = [7,6,4,3,1]cash never improves (every sell would lose) → 0.
Pitfalls
- Updating hold from the just-updated cash instead of prevCash — muddles the model (harmless here, wrong once a fee/cooldown is added).
- Initializing hold to 0 instead of -∞ — pretends you own a free share.
- Adding a transaction counter you don't need — transactions are unlimited.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int maxProfit(int[] prices) { int profit = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]) { profit += prices[i] - prices[i - 1];Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Treating it as a single buy/sell (Stock I)
Finding one min and one later max ignores that you can re-enter. On [1,2,1,2] the single-trade answer is 1, but capturing both up-steps gives 2.
Explore the code comparisonHide the code comparison
Treating it as a single buy/sell (Stock I)
Finding one min and one later max ignores that you can re-enter. On [1,2,1,2] the single-trade answer is 1, but capturing both up-steps gives 2.
Don't write this
min_price, best = prices[0], 0
for p in prices:
min_price = min(min_price, p)
best = max(best, p - min_price)
return bestWrite this instead
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
return profit2Buying at a valley but waiting for the global peak
Holding through a dip forfeits the smaller swings. You must sell at every local peak and rebuy at every local valley — equivalently, add every positive delta.
Explore the code comparisonHide the code comparison
Buying at a valley but waiting for the global peak
Holding through a dip forfeits the smaller swings. You must sell at every local peak and rebuy at every local valley — equivalently, add every positive delta.
Don't write this
// buy at the lowest valley, sell only at the single highest later day
int buy = min(prices);
int sell = maxAfter(buy);
return sell - buy;Write this instead
int profit = 0;
for (int i = 1; i < prices.length; i++)
if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
return profit;3Initializing the DP hold state to 0
hold = 0 implies you start already owning a share for free, inflating profit. It must be -∞ (or -prices[0] after the first day) so the first buy is paid for.
Explore the code comparisonHide the code comparison
Initializing the DP hold state to 0
hold = 0 implies you start already owning a share for free, inflating profit. It must be -∞ (or -prices[0] after the first day) so the first buy is paid for.
Don't write this
cash, hold = 0, 0Write this instead
cash, hold = 0, float('-inf')Revise
Carry the pattern into the interview
Pattern to remember
Greedy — sum of positive consecutive deltas
Code pattern to memorize
profit = 0
for i in 1..n-1:
if prices[i] > prices[i-1]:
profit += prices[i] - prices[i-1]
return profitRules to remember
- 1Add up every positive delta
prices[i] − prices[i−1]; ignore non-positive ones. - 2This equals buying at every valley and selling at every peak — the two views are identical.
- 3Unlimited transactions is the key permission; with a limit, greedy breaks and you need DP.
- 4You may sell and rebuy the same day, so capturing each up-step independently is legal.
- 5The greedy result is provably optimal because gains telescope: a long climb = sum of its daily steps.
Use this pattern when
- Unlimited buy/sell transactions on a price (or value) series
- Maximize total gain from any sequence of up-moves
- Problems framed as 'capture all upward movement'
- When holding one unit at a time and same-day re-entry is allowed
Choose another pattern when
- At most k (or 1, or 2) transactions → DP over (day, transactions, holding) — greedy fails
- Cooldown or transaction fee → DP state machine (LC 309 / 714)
- Must hold across the whole period → that's Stock I (single buy/sell, track min)
- Short selling allowed → the 'only capture ups' argument no longer holds
Interview takeaway
When transactions are unlimited, the answer collapses to 'grab every up-step'. Internalize the telescoping proof — it turns a scary 'when to buy and sell' search into a one-line sum, and it cleanly contrasts with the DP needed once a transaction cap appears.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternGreedy capture of positive deltas for unlimited-transaction profit, with the cash/hold DP as the generalizable backbone. Recognise the greedy whenever local choices are independent; switch to the DP state machine the moment a transaction cap, fee, or cooldown couples the decisions.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Best Time to Buy and Sell StockExactly one transaction — track the running minimum and best single profit.
- Best Time to Buy and Sell Stock IIIComing soonAt most two transactions — DP with buy1/sell1/buy2/sell2 states.
- Best Time to Buy and Sell Stock IVComing soonAt most k transactions — generalize the state machine over k.
- Best Time to Buy and Sell Stock with Transaction FeeComing soonUnlimited transactions but subtract a fee per sale — the cash/hold DP with hold + p − fee.