Dynamic Programming • State Machine

Best Time to Buy and Sell Stock with Cooldown

Maximize your profit from stock trading with one restriction: after you sell your stock, you cannot buy stock on the next day (i.e., cooldown 1 day).

Try Interactive Simulator

Overview

This is best modeled as a finite state machine. On any given day, your portfolio can be in one of three states: Holding Stock (Buy), Just Sold (Sell), or Empty (Cooldown).

The Buy State

To enter the `Buy` state today, you either stay in `Buy` from yesterday, or you buy today. But you can ONLY buy today if you were in the `Cooldown` state yesterday.

The Sell State

To enter the `Sell` state today, you either stay in `Sell` from yesterday (doing nothing), or you sell the stock you were holding in the `Buy` state.

The Cooldown State

The `Cooldown` state is forced. If you sell today, tomorrow you MUST be in cooldown. So tomorrow's `Cooldown` profit is just today's `Sell` profit.

Day 0: Price $1

Buy State

-1

→

Sell State

0

→

Cooldown

0

Code Tracker

:::

1let buy = -prices[0];

2let sell = 0;

3let cool = 0;

4for (let i = 1; i < prices.length; i++) {

5 let prevBuy = buy;

6 let prevSell = sell;

7 // We can only buy if we were in cooldown yesterday

8 buy = Math.max(prevBuy, cool - prices[i]);

9 // We can only sell if we bought previously

10 sell = Math.max(prevSell, prevBuy + prices[i]);

11 // Cooldown happens the day after selling

12 cool = prevSell;

13}

14return Math.max(sell, cool);

Stock With Cooldown

Stock With Cooldown

Best Time to Buy and Sell Stock with Cooldown

Overview

The Buy State

The Sell State

The Cooldown State

Best Time to Buy and Sell Stock with Cooldown

Overview

The Buy State

The Sell State

The Cooldown State