← DSA Atlas
Dedicated problem page · #123

Best Time to Buy and Sell Stock III

HardStock and State-Machine DPFour-state transaction machineState-machine DP with fixed transaction cap
Solve on LeetCode ↗
123
HardStock and State-Machine DPState-machine DP with fixed transaction capFour-state transaction machine

Best Time to Buy and Sell Stock III

Given an array prices where prices[i] is the price of a stock on day i, find the maximum profit you can achieve completing at most two transactions. You may not hold more than one share at a time and must sell before buying again.

Open official problem prompt ↗
In plain English

Maximize profit when at most two complete buy-sell round trips are allowed.

Picture it like this

Like a relay with exactly two legs: the money you finish the first leg with becomes the capital you carry into the second, so each stage builds on the one before it.

Example
Input
prices = [3, 3, 5, 0, 0, 3, 1, 4]
Output
6
Why
Buy at 0 (day 4) sell at 3 (day 6) is +3, then buy at 1 (day 7) sell at 4 (day 8) is +3; total 6.
Constraints
1 <= prices.length <= 10^50 <= prices[i] <= 10^5
Pattern lesson

See the pattern, then code

Four-state transaction machine
Recognition clue

A hard cap of exactly two transactions signals a small fixed-width state machine rather than the unlimited greedy of problem 122.

↗
Stock and State-Machine DP

A small set of modes such as holding, free, cooldown, or transactions left.. Track four running best values as you sweep prices: the best position after the first buy, after the first sell, after the second buy, and after the second sell. Each transition reuses the profit banked by the previous stage.

New words, made simpleKnow these before the algorithm
State
A stage of the machine: holding after buy 1, cashed out after sell 1, holding after buy 2, or cashed out after sell 2.
buy1 / buy2
Best profit while currently holding a share during the first / second transaction.
sell1 / sell2
Best profit after completing the first / second sale.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Left/right split

Correct and intuitive but uses extra arrays and does not generalize to k transactions.

For each day compute best one-transaction profit to its left and to its right, then maximize the sum.

Time O(n)Space O(n)
Best choiceFour rolling states

Constant space, single pass, and generalizes directly to the k-transaction problem.

Keep buy1, sell1, buy2, sell2 and relax them left to right.

Time O(n)Space O(1)
The rule we keep true

Invariant

After each price, sell2 holds the maximum profit achievable with at most two transactions considering prices seen so far.

Why this is correct

Reasoning

Each state is defined as the best achievable value entering that stage, and every transition only draws on an earlier stage that was itself already optimized; because buy2 subtracts the current price from the already-maximized sell1, the two transactions are forced to be non-overlapping in the profit accounting.

The algorithm in three movesSay these aloud before coding
1Initialize buy1 and buy2 to negative infinity, sell1 and sell2 to 0

after day 4: buy2 = 2, sell1 = 2

2For each price, update buy1 = max(buy1, -price)

after day 6: sell1 = 3, sell2 = 5

3Update sell1 = max(sell1, buy1 + price)

after day 8: sell2 = 6

4Update buy2 = max(buy2, sell1 - price) then sell2 = max(sell2, buy2 + price)

5Return sell2

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
30
31
52
03
04
35
16
47
1 · Readprice 0
2 · AskImprove any state?
3 · Update statebuy1=0, sell1=2, buy2=2, sell2=2
4 · Resultbuy1 rises to 0 (buying cheapest), buy2 rises to 2.
Key takeaway

Two disjoint profitable windows: buy at 0 sell at 3, then buy at 1 sell at 4.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Seed states

    No share held costs nothing (sells = 0); holding a share starts impossibly bad (buys = -inf).

  2. 2
    Lines 6-7First transaction

    buy1 tracks the cheapest entry; sell1 the best first-trade profit.

  3. 3
    Lines 8-9Second transaction

    buy2 reinvests sell1's profit minus today's price; sell2 closes the second trade.

  4. 4
    Lines 10Answer

    sell2 dominates sell1 (doing fewer trades is always allowed), so it is the maximum.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Monotonically decreasing prices give 0
  • When one big trade beats two, sell2 still equals sell1 because a second trade can be a no-op
  • Single element returns 0
!

Common beginner mistakes

  • Updating buy2 before sell1 within the same iteration is fine because sell1 was just relaxed, but reordering sell2 before buy2 breaks it
  • Forgetting that at most two means fewer is allowed, so never force two trades
  • Using per-day left/right arrays and running out of memory at 10^5 length is avoidable with the rolling form
Check your understanding

Why is it correct to update all four variables in sequence within the same loop iteration?

More in Stock and State-Machine DP

#122Best Time to Buy and Sell Stock IIGreedy on consecutive gains#188Best Time to Buy and Sell Stock IVk-transaction state machine#714...with Transaction FeeCash/hold state machine with per-sale fee