#123 Best Time to Buy and Sell Stock III
the problem
In plain words
prices[i] is a stock's price on day i. You may complete at most two trades (a trade is a buy followed by a later sell) and you can never hold more than one share. Return the largest total profit.
in prices = [3,3,5,0,0,3,1,4]
out 6
Buy at 0, sell at 3; then buy at 1, sell at 4: 3 + 3 = 6.
in prices = [1,2,3,4,5]
out 4
One trade, 1 → 5, is already the best.
in prices = [7,6,4,3,1]
out 0
- 1 ≤ prices.length ≤ 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
patternState-machine DP
Four states form a chain: after the first buy, after the first sell, after the second buy, after the second sell. Every day each state either stays as it is or takes one step along the chain.
solutions
From brute force to optimal
best(day, buysLeft, holding): rest, buy (if a buy is left), or sell.
- Past the last day → 0.
- rest = best(day + 1, …).
- Holding → sell; empty-handed with buysLeft > 0 → buy.
- Return the larger.
Act or wait every day, nothing cached.
Recursion depth n.
class Solution { public int maxProfit(int[] prices) { return best(prices, 0, 2, false); } /** Best profit from day i on, with `buysLeft` purchases still allowed. */ private int best(int[] prices, int i, int buysLeft, boolean holding) { if (i == prices.length) return 0; int rest = best(prices, i + 1, buysLeft, holding); // do nothing today int act = 0; if (holding) act = prices[i] + best(prices, i + 1, buysLeft, false); // sell else if (buysLeft > 0) act = -prices[i] + best(prices, i + 1, buysLeft - 1, true); // buy return Math.max(rest, act); }}Two trades never overlap, so some day separates them: best one trade on the left + best one trade on the right.
- left[i] = best single trade within days 0..i (running minimum).
- right[i] = best single trade within days i..n−1 (running maximum from the right).
- Answer = max over i of left[i] + right[i].
Three linear passes.
The left and right arrays.
class Solution { public int maxProfit(int[] prices) { int n = prices.length; int[] left = new int[n]; // left[i]: best single trade inside days 0..i int[] right = new int[n]; // right[i]: best single trade inside days i..n-1 int low = prices[0]; for (int i = 1; i < n; i++) { low = Math.min(low, prices[i]); left[i] = Math.max(left[i - 1], prices[i] - low); } int high = prices[n - 1]; for (int i = n - 2; i >= 0; i--) { high = Math.max(high, prices[i]); right[i] = Math.max(right[i + 1], high - prices[i]); } int best = 0; for (int i = 0; i < n; i++) best = Math.max(best, left[i] + right[i]); // first trade ends by i, second starts at i return best; }}buy1, sell1, buy2, sell2 — each one stays or steps from the state before it.
- buy1 = buy2 = −prices[0], sell1 = sell2 = 0.
- Each day: buy1 = max(buy1, −p); sell1 = max(sell1, buy1 + p); buy2 = max(buy2, sell1 − p); sell2 = max(sell2, buy2 + p).
- Return sell2.
Four max() per day.
Four ints.
class Solution { public int maxProfit(int[] prices) { int buy1 = -prices[0], sell1 = 0; // after the 1st buy / the 1st sell int buy2 = -prices[0], sell2 = 0; // after the 2nd buy / the 2nd sell for (int p : prices) { buy1 = Math.max(buy1, -p); // keep, or make the first buy today sell1 = Math.max(sell1, buy1 + p); // keep, or sell the first share today buy2 = Math.max(buy2, sell1 - p); // keep, or buy again using the first profit sell2 = Math.max(sell2, buy2 + p); // keep, or sell the second share today } return sell2; // sell2 >= sell1: a same-day buy + sell costs nothing }}in the room
How to say it in the interview
talk track
- "Two trades never overlap, so a day splits them: best trade on the left + best on the right." That's the O(n)-memory version.
- "The same thing is a machine with four states" — buy1, sell1, buy2, sell2 — O(1) memory.
- Point out that k trades (LC 188) is the same chain with 2k states.
traps
- Taking the two biggest single rises: they can overlap in time.
- Starting buy1/buy2 at Integer.MIN_VALUE and then adding a price in a different update order can overflow; start them at −prices[0].
what they ask next
Follow-ups
At most k trades?
LC 188: arrays buy[t], sell[t] for t = 1..k — O(n·k).
Return the actual buy and sell days?
Use the split version: record where left[] and right[] last improved, then pick the best split day.
before you submit
Edge cases to test
- One day → 0.
- A steady rise needs one trade: [1,2,3,4,5] → 4.
- Three good rises but room for two: [1,2,4,2,5,7,2,4,9,0] → 13.
practise next
Similar problems
- #188Best Time to Buy and Sell Stock IVHardin DP Patterns
- #121Best Time to Buy and Sell StockEasyin Arrays & Strings