Best Time to Buy and Sell Stock II
Problem
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 (buying and selling on the
same day is allowed). Return the maximum total profit.[7,1,5,3,6,4]Output7[1,2,3,4,5]Output4[7,6,4,3,1]Output01 ≤ n ≤ 3·104 · 0 ≤ prices[i] ≤ 104
Try it yourself
class Solution {
public int maxProfit(int[] prices) {
}
}
Instinct "In place", "O(1) extra space" or "one pass" over an array? Think write pointer, reversal, prefix/suffix passes or using indices as storage.
Memory hack Read fast, write slow, reverse to rotate, and let the index be the hash.
Open the Array Manipulation guide →Approaches
Brute ForceRecursion — Try Every Decision
O(2n)Space O(n)On each day you either do nothing, or act (buy if empty-handed, sell if holding). Recursively explore both branches and keep the better profit. Exhaustive, so obviously correct.
public int maxProfit(int[] prices) { return solve(prices, 0, false); } private int solve(int[] p, int i, boolean holding) { if (i == p.length) return 0; int skip = solve(p, i + 1, holding); int act = holding ? p[i] + solve(p, i + 1, false) // sell : -p[i] + solve(p, i + 1, true); // buy return Math.max(skip, act); }
Explores 2n paths — only usable for tiny inputs.
BetterDP — Hold / Free States
O(n)Space O(n)The recursion only depends on (day, holding), so tabulate it.
hold[i] = best profit ending day i with a share, free[i] = without
one. Each day: keep the state, or buy/sell to switch.
public int maxProfit(int[] prices) { int n = prices.length; int[] hold = new int[n], free = new int[n]; hold[0] = -prices[0]; for (int i = 1; i < n; i++) { hold[i] = Math.max(hold[i - 1], free[i - 1] - prices[i]); free[i] = Math.max(free[i - 1], hold[i - 1] + prices[i]); } return free[n - 1]; }
Linear and generalises to cooldown/fee variants, but stores two arrays.
OptimalGreedy — Sum Positive Differences
O(n)Space O(1)A climb from valley to peak equals the sum of its daily steps, so adding every
prices[i] - prices[i-1] > 0 captures every rising run (same total as the
peak–valley method). Down days are skipped, i.e. you simply aren't holding.
public 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]; // ride every rise } } return profit; }
Dry run[7,1,5,3,6,4]
- i=17p1i5364fall → skip, 0
- i=271p5i364+4 → profit=4
- i=3715p3i64fall → skip
- i=47153p6i4+3 → profit=7
- i=571536p4ifall → 7 ✔
One pass, O(1) memory, three lines of logic.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Recursion — Try Every Decision | O(2n) | O(n) |
| Better | DP — Hold / Free States | O(n) | O(n) |
| Optimal | Greedy — Sum Positive Differences | O(n) | O(1) |
- Solving Stock I (single trade) by mistake — here trades are unlimited.
- Holding two shares at once in the recursion — buy only when not holding.
- Returning
hold[n-1]instead offree[n-1]— ending with a share is never better.
- Prove the greedy: any span's profit = sum of its daily deltas.
- Present the DP first if the interviewer hints at fee/cooldown variants.
- Mention the DP rolls into two variables → O(1) space as well.