#122 Best Time to Buy and Sell Stock II
the problem
In plain words
prices[i] is a stock's price on day i. You may trade as many times as you like, but you can hold at most one share at a time, so you must sell before you buy again. Buying and selling on the same day is allowed. Return the maximum total profit.
in prices = [7,1,5,3,6,4]
out 7
Buy at 1, sell at 5 (+4); buy at 3, sell at 6 (+3).
in prices = [1,2,3,4,5]
out 4
Buy at 1, sell at 5 — the same as adding every one-day rise.
in prices = [7,6,4,3,1]
out 0
Prices only fall, so never trade.
- 1 ≤ n ≤ 3·10⁴
- 0 ≤ prices[i] ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGreedy choice
A trade from a low day to a high day earns exactly the sum of the daily rises in between. So collect every day-to-day rise and skip every fall — no plan can do better.
solutions
From brute force to optimal
Recursion over the days with one flag: do I hold a share? Each day, either act (buy or sell) or do nothing.
- best(day, holding): 0 when day == n.
- skip = best(day + 1, holding).
- act = sell (price + best(day + 1, false)) or buy (−price + best(day + 1, true)).
- Return max(skip, act).
Two choices per day and nothing is remembered — the call tree doubles every level.
The recursion goes one level deep per day.
class Solution { public int maxProfit(int[] prices) { return best(prices, 0, false); } /** Best profit from day onwards, knowing whether we already hold a share. Two choices a day: O(2^n). */ private int best(int[] prices, int day, boolean holding) { if (day == prices.length) return 0; int skip = best(prices, day + 1, holding); // do nothing today int act = holding ? prices[day] + best(prices, day + 1, false) // sell today : -prices[day] + best(prices, day + 1, true); // buy today return Math.max(skip, act); }}For every pair of neighbouring days, if the price went up, bank the difference.
- profit = 0.
- For i from 1: rise = prices[i] − prices[i − 1].
- If rise > 0, profit += rise.
One pass, one subtraction per day.
One running total.
class Solution { public int maxProfit(int[] prices) { int profit = 0; for (int i = 1; i < prices.length; i++) { int rise = prices[i] - prices[i - 1]; if (rise > 0) profit += rise; // bank every up-day: buy yesterday, sell today } return profit; }}Track the best profit while holding nothing (cash) and while holding one share (hold), updating both each day.
- cash = 0, hold = −prices[0].
- newCash = max(cash, hold + price) — stay out or sell.
- newHold = max(hold, cash − price) — keep holding or buy.
- Answer: cash.
Constant work per day.
Two variables (plus two temporaries).
class Solution { public int maxProfit(int[] prices) { int cash = 0; // best profit so far while holding nothing int hold = -prices[0]; // best profit so far while holding one share for (int i = 1; i < prices.length; i++) { int newCash = Math.max(cash, hold + prices[i]); // stay out, or sell today int newHold = Math.max(hold, cash - prices[i]); // keep holding, or buy today cash = newCash; hold = newHold; } return cash; // ending with a share in hand is never better }}in the room
How to say it in the interview
talk track
- Draw the prices as a line chart: the answer is the total height of all the upward segments.
- Prove it in one line: a valley-to-peak trade earns exactly the sum of the rises between them, and falls never have to be paid for.
- Offer the cash/hold DP if the interviewer adds a fee or a cooldown — the greedy sum stops working there.
traps
- Reusing the one-trade code from LC 121 — it returns 5, not 7, on example 1.
- Thinking you must actually trade every day: the greedy sum is accounting. The real trades are valley → peak.
what they ask next
Follow-ups
With a transaction fee (LC 714)?
Use the cash/hold DP and subtract the fee when you sell: newCash = max(cash, hold + price − fee).
With a one-day cooldown after selling (LC 309)?
Add a third state, "just sold", to the DP — the DP Patterns chapter builds it step by step.
At most k transactions (LC 188)?
DP over (transactions used, holding or not): O(n·k).
before you submit
Edge cases to test
- One day → 0.
- Prices only fall, or stay flat → 0.
- A steady rise ([1,2,3,4,5] → 4): one long trade equals four one-day trades.
practise next
Similar problems
- #121Best Time to Buy and Sell StockEasyin Arrays & Strings
- #53Maximum SubarrayMediumin Arrays & Strings