Best Time to Buy and Sell Stock III

HardDP · State Machine🧩 State Machine DP LeetCode #123 ↗Updated Oct 30, 2026

Problem

prices[i] is a stock's price on day i. You may complete at most two buy→sell transactions, and you can hold at most one share at a time (sell before buying again). Return the maximum total profit, or 0 if no trade helps.

Input[3,3,5,0,0,3,1,4]Output6

Input[1,2,3,4,5]Output4

Input[7,6,4,3,1]Output0

1 ≤ n ≤ 10⁵ · 0 ≤ prices[i] ≤ 10⁵ · at most 2 transactions, no overlap

Try it yourself

Java

class Solution {
    public int maxProfit(int[] prices) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Model each day with four running bests: buy1, sell1, buy2, sell2 (max cash after each action). Each one depends only on the previous state, so one pass with four variables solves it.

PatternState Machine DP

Instinct Each step you are in one of a few modes (holding, sold, cooling down) with rules for switching - keep one DP value per mode and update all of them every step.

Memory hack Name the moods, draw the moves, max the arrows - every arrow in your state diagram becomes exactly one line of code.

Open the State Machine DP guide →

Approaches

Brute ForceSplit Day + Naive One-Transaction Scan

Time O(n³)Space O(1)

Two non-overlapping trades are separated by some split day k: one lies in [0..k], the other in [k..n-1]. For each k, find the best single trade on each side by trying every buy/sell pair. (A single trade is the case where one side earns 0.)

Java

public int maxProfit(int[] prices) {
    int n = prices.length, best = 0;
    for (int k = 0; k < n; k++)
        best = Math.max(best, one(prices, 0, k) + one(prices, k, n - 1));
    return best;
}
private int one(int[] p, int lo, int hi) { // best single trade in p[lo..hi]
    int best = 0;
    for (int i = lo; i <= hi; i++)
        for (int j = i + 1; j <= hi; j++)
            best = Math.max(best, p[j] - p[i]);
    return best;
}

Obviously correct, but n × n² work is hopeless at n = 10⁵.

BetterPrefix & Suffix Best (Forward–Backward)

Time O(n)Space O(n)

Precompute left[i] = best single trade within days 0..i (track the running minimum) and right[i] = best within i..n-1 (track the running maximum from the right). The answer is max(left[i] + right[i]) over all split days.

Java

public int maxProfit(int[] prices) {
    int n = prices.length;
    int[] left = new int[n], right = new int[n];
    for (int i = 1, min = prices[0]; i < n; i++) {
        min = Math.min(min, prices[i]);
        left[i] = Math.max(left[i - 1], prices[i] - min);
    }
    for (int i = n - 2, max = prices[n - 1]; i >= 0; i--) {
        max = Math.max(max, prices[i]);
        right[i] = Math.max(right[i + 1], max - prices[i]);
    }
    int best = 0;
    for (int i = 0; i < n; i++) best = Math.max(best, left[i] + right[i]);
    return best;
}

Linear time, but two extra arrays of size n.

OptimalState Machine DP (4 Variables)

Time O(n)Space O(1)

States in order: buy1 (holding 1st share), sell1 (done 1), buy2 (holding 2nd), sell2 (done 2). Each day: keep the state or take the action from the previous state, e.g. buy2 = max(buy2, sell1 - p). This is a dp[n][5] table with the day dimension dropped; same-day updates are safe because buying and selling on one day nets 0.

Java

public int maxProfit(int[] prices) {
    int buy1 = Integer.MIN_VALUE, sell1 = 0;
    int buy2 = Integer.MIN_VALUE, sell2 = 0;
    for (int p : prices) {
        buy1 = Math.max(buy1, -p);          // buy 1st share
        sell1 = Math.max(sell1, buy1 + p);  // sell 1st share
        buy2 = Math.max(buy2, sell1 - p);   // buy 2nd with profit 1
        sell2 = Math.max(sell2, buy2 + p);  // sell 2nd share
    }
    return sell2;
}

Dry run[3,3,5,0,0,3,1,4]

p current day changed

i=0
3
p
3

5

0

0

3

1

4

b1=-3 s1=0 b2=-3 s2=0
i=2
3

3

5
p
0

0

3

1

4

b1=-3 s1=2 b2=-3 s2=2
i=3
3

3

5

0
p
0

3

1

4

b1=0 s1=2 b2=2 s2=2
i=5
3

3

5

0

0

3
p
1

4

b1=0 s1=3 b2=2 s2=5
i=7
3

3

5

0

0

3

1

4
p
b1=0 s1=4 b2=2 s2=6 ✔

One pass, four integers — and it generalises to k transactions.

Pro tip

For at most k trades, use arrays buy[k], sell[k] with buy[j] = max(buy[j], sell[j-1] - p) — that is Stock IV (188).

At a glance

Level	Approach	Time	Space
Brute Force	Split Day + Naive One-Transaction Scan	`O(n³)`	`O(1)`
Better	Prefix & Suffix Best (Forward–Backward)	`O(n)`	`O(n)`
Optimal	State Machine DP (4 Variables)	`O(n)`	`O(1)`

Common pitfalls

Summing the two largest single-trade gains — they may overlap in time.
Initialising buy states to 0 — implies a free share; use -∞ or -prices[0].
Forcing exactly two trades — one trade (or none) can be optimal.

Interview tips

Start from Stock I (one trade), then ask “where does the 2nd trade start?”.
Draw the 5-state chain: rest → buy1 → sell1 → buy2 → sell2.
Mention the k-transaction generalisation and the O(nk) cost.

Pattern

State machine DP → sequential decisions with a few modes (holding / not, count used) where each day depends only on yesterday.

My notes saved in this browser