AlgoViz
HomeDynamic Programming

Best time to buy and sell stock III

Medium

Four states across the day

Problem

Maximize profit with at most two transactions.

In simple words

Track buy/sell profit for the first and second transaction as you scan, chaining them together.

The idea

Track the best value after the first buy, first sell, second buy and second sell, updating them in order each day. Each state depends only on the previous one, so the whole thing runs in O(n) with four variables.

The trick

  • Update in order: buy1, sell1, buy2, sell2.
  • buy2 builds on sell1 — the second transaction starts from the first's profit.
  • O(n) time, O(1) space.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

3
3
5
0
0
3
1
4
0
1
2
3
4
5
6
7

Step 1 of 2. Here's the example — [3,3,5,0,0,3,1,4] Values: 3, 3, 5, 0, 0, 3, 1, 4.

1/2
Optimal
timeO(n)spaceO(1)
1buy1=buy2=-inf; sell1=sell2=02for p: buy1=max(buy1,-p); sell1=max(sell1,buy1+p); buy2=max(buy2,sell1-p); sell2=max(sell2,buy2+p)

Input

array
[3, 3, 5, 0, 0, 3, 1, 4]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
prices = [3, 3, 5, 0, 0, 3, 1, 4]
Output:
6
Explanation:
Two trades earn 6 total.

Example 2

Input:
prices = [1, 2, 3, 4, 5]
Output:
4
Explanation:
One rising trade → 4.

Example 3

Input:
prices = [7, 6, 4, 3, 1]
Output:
0
Explanation:
Only falls → 0.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.