Dynamic Programming • State Machines

Best Time to Buy and Sell Stock III

Maximize your profit given you can complete at most two transactions.

Overview

You can complete at most two transactions. We model this as a state machine with 4 states: after 1st buy, after 1st sell, after 2nd buy, after 2nd sell.

State Transitions

Each state can either stay as is (don't transact today) or transition to the new state by transacting at today's price.

DP Table Compression

Since the state on day i only depends on the state on day i-1, we can compress the DP table into just 4 variables.

Key Insight

The states are updated sequentially. We can safely update them in place because the updated previous state will only increase our current state's potential.

Day 13

Day 23

Day 35

Day 40

Day 50

Day 63

Day 71

Day 84

Code Tracker

:::

1let buy1 = -Infinity, sell1 = 0;

2let buy2 = -Infinity, sell2 = 0;

3for (let price of prices) {

4 buy1 = Math.max(buy1, -price);

5 sell1 = Math.max(sell1, buy1 + price);

6 buy2 = Math.max(buy2, sell1 - price);

7 sell2 = Math.max(sell2, buy2 + price);

8}

Best Time To Buy Sell Stock Iii

Best Time To Buy Sell Stock Iii

Best Time to Buy and Sell Stock III

Overview

State Transitions

DP Table Compression

Key Insight

Best Time to Buy and Sell Stock III

Overview

State Transitions

DP Table Compression

Key Insight