DSA problem

Best Time to Buy and Sell Stock with Cooldown

MediumState Machine DPPattern: State Machine DPtop300AmazonMicrosoftGoogleBloombergAdobe

You are given an array prices where prices[i] is the price of a given stock on the i-th day. Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restriction: after you sell your stock, you cannot buy stock on the next day (i.e., there is a one-day cooldown). Note: You may not engage in multiple transactions simultaneously — you must sell the stock before you buy again.

The cooldown rule turns the otherwise greedy unlimited-transaction problem (sum every positive delta) into something subtler. After a sell, the next day must pass through a "resting" state before another buy is allowed; this forbids the greedy collection of every tiny up-tick. The natural framing is a three-state machine: held (currently own the stock), sold (just sold today, cannot buy tomorrow), and rest (idle, free to buy).

Transitions on day i with price p are: from rest we may either stay in rest or buy and move to held; from held we may either stay in held or sell and move to sold; from sold we are forced into rest on the next day (we cannot buy). Encoded as DP, rest on day i is the max of yesterday's rest and yesterday's sold; held is the max of yesterday's held and yesterday's rest minus p; sold is yesterday's held plus p.

The optimal implementation collapses to three rolling scalars. Order of updates matters because the new value of sold depends on the old held, and the new rest depends on the old sold. The cleanest order is: compute sold = held + p first, then update held = max(held, rest - p) using the still-old rest, then update rest = max(rest, prev_sold) using the value of sold from before this day's sell. The final answer is max(sold, rest) because we should not end the period still holding stock.

Examples

Example 1

Input: prices = [1,2,3,0,2]

Output: 3

Explanation: Buy on day 1 (price = 1) and sell on day 2 (price = 2) for profit 1. Cooldown day 3. Buy on day 4 (price = 0) and sell on day 5 (price = 2) for profit 2. Total profit is 3.

Example 2

Input: prices = [1]

Output: 0

Explanation: With only one day there is no opportunity to both buy and sell, so the best is to stay idle.

Example 3

Input: prices = [1,2,4]

Output: 3

Explanation: Buy on day 1 (price = 1) and sell on day 3 (price = 4) for profit 3. The cooldown rule does not bite because no second transaction is needed.

Constraints

1 <= prices.length <= 5000
0 <= prices[i] <= 1000
After you sell your stock, you cannot buy stock on the next day (one-day cooldown).
You may not engage in multiple transactions simultaneously.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

dynamic-programmingstate-machinearray

Browse all DSA problems