Dynamic Programming • State Machines

Best Time to Buy and Sell Stock IV

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

Overview

You can complete at most K transactions. We model this as a state machine where each transaction j up to K has its own buy and sell state.

Generalization

This is exactly like Stock III, but generalized to K transactions using arrays instead of discrete variables.

Space Optimization

We only need the previous transaction's sell state to compute the current transaction's buy state, leading to O(K) space.

Key Insight

Notice how `sell[j-1]` is used to transition into `buy[j]`. We can use today's price to buy the stock using the profit we made from the previous j-1 transactions.

k =

Day 13

Day 22

Day 36

Day 45

Day 50

Day 63

Code Tracker

:::

1let buy = Array(k + 1).fill(-Infinity);

2let sell = Array(k + 1).fill(0);

3for (let price of prices) {

4 for (let j = 1; j <= k; j++) {

5 buy[j] = Math.max(buy[j], sell[j - 1] - price);

6 sell[j] = Math.max(sell[j], buy[j] + price);

7 }

8}

Best Time To Buy Sell Stock Iv

Best Time To Buy Sell Stock Iv

Best Time to Buy and Sell Stock IV

Overview

Generalization

Space Optimization

Key Insight

Best Time to Buy and Sell Stock IV

Overview

Generalization

Space Optimization

Key Insight