Best Time to Buy and Sell Stock with Cooldown

Best Time to Buy and Sell Stock with Cooldown is where state machine DP shines. The interviewer wants to see if you can track a few states and the moves between them. Once you name the states, the transitions almost write themselves.

🎯 The Problem

You get an array of daily stock prices. You want the most total profit you can make.

• You can buy and sell as many times as you want.
• After you sell, you must rest one day before you can buy again. That forced rest is the cooldown.
• You can hold at most one share at a time.
• For prices [1, 2, 3, 0, 2]: buy at 1, sell at 3, rest a day, buy at 0, sell at 2. Profit is 2 + 1 = 3.
• The cooldown is the reason you cannot squeeze out more.

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

Explanation: buy at 1, sell at 3, cooldown one day,
buy at 0, sell at 2. Profit = 2 + 1 = 3.

Each day you are in one of three situations. You are holding a stock, you just sold and must rest, or you are free to buy. We track all three.

🐢 Approach 1: Plain Recursion (Brute Force)

The idea in one line: try every legal move each day and keep the best profit.

The idea:

• A function takes the day number and whether you hold a stock.
• It tries every legal move and returns the best profit from there.

How it works:

• If you do not own a stock, you can buy or skip.
• If you own one, you can sell or keep holding.
• After a sell, the next day must be a rest.
• At the end of the prices, return zero. Nothing more to earn.

Why it is weak:

• It branches at every day.
• The same day and holding state get re-solved on many paths.
• So the time grows exponentially.

Here is the plain recursion code:

def max_profit(prices):
    def dfs(i, holding):
        if i >= len(prices):
            return 0
        if holding:
            sell = prices[i] + dfs(i + 2, False)
            keep = dfs(i + 1, True)
            return max(sell, keep)
        buy = -prices[i] + dfs(i + 1, True)
        skip = dfs(i + 1, False)
        return max(buy, skip)

    return dfs(0, False)

⚡ Approach 2: Memoization (Better)

The idea in one line: cache each solved state so the recursion never repeats work.

The idea:

• The best profit from “day d, holding or not” never changes.
• So store it the first time and read it after.

How it works:

• Keep a table keyed by the day and the holding flag.
• First time a state is solved, save it.
• Next time it shows up, read the saved value.

Why it is fast:

• Each state is solved only once. This is memoization.
• The time drops from exponential to O(n).
• The cost is O(n) memory for the table.

Here is the memoized recursion:

from functools import lru_cache


def max_profit(prices):
    @lru_cache(None)
    def dfs(i, holding):
        if i >= len(prices):
            return 0
        if holding:
            return max(prices[i] + dfs(i + 2, False), dfs(i + 1, True))
        return max(-prices[i] + dfs(i + 1, True), dfs(i + 1, False))

    return dfs(0, False)

⚡ Approach 3: State Machine Tabulation (Better)

The idea in one line: name three daily states and build the answer from the bottom up.

The idea:

• hold is the best profit when you own a stock at day’s end.
• sold is the best profit on the day you just sold.
• rest is the best profit when you own nothing and are free to buy.
• State machine DP tracks these named states and the moves between them.

The transitions:

• Today’s hold is the better of staying held, or buying today from yesterday’s rest.
• Today’s sold is yesterday’s hold plus today’s price.
• Today’s rest is the better of yesterday’s rest or yesterday’s sold.

Why it is solid:

• No recursion, just a table filled day by day.
• The cooldown lives entirely in rest, which only fills from yesterday’s sold.
• Time is O(n), space is O(n) for the table.

Here is the tabulation code:

def max_profit(prices):
    if not prices:
        return 0

    hold = -prices[0]
    sold = 0
    rest = 0

    for price in prices[1:]:
        prev_hold, prev_sold, prev_rest = hold, sold, rest
        hold = max(prev_hold, prev_rest - price)
        sold = prev_hold + price
        rest = max(prev_rest, prev_sold)

    return max(sold, rest)

🚀 Approach 4: Space-Optimized Three Variables (Best)

The idea in one line: each day depends only on yesterday, so keep just three rolling numbers.

The idea:

• Every new day needs only the three values from the day before.
• So drop the arrays and roll three numbers forward.

How it works:

• Start hold very negative, sold at 0, rest at 0.
• Each day compute the new three values from the old three.
• Save yesterday’s hold and sold before overwriting them.
• At the end, the answer is the larger of sold and rest.

Why it is best:

• Same O(n) time as the table.
• Only three numbers, so O(1) extra memory.
• Holding a stock at the end is never best, so we ignore hold at the finish.

Here is the state machine running across the days. Profit flows between the three states.

Steps to Solve

1. Set hold to a very negative number. Set sold to 0 and rest to 0.
2. Loop over each price in the array.
3. Save the old hold and old sold before changing anything.
4. Update hold to the larger of old hold or rest - price. This is keep holding or buy today.
5. Update sold to old hold plus price. This is selling today.
6. Update rest to the larger of rest or old sold. This is resting or cooling down after a sale.
7. After the loop, return the larger of sold and rest.

#include <stdio.h>
#include <limits.h>

int max(int a, int b) { return a > b ? a : b; }

int maxProfit(int prices[], int n) {
    int hold = INT_MIN;   // own a stock
    int sold = 0;         // just sold today
    int rest = 0;         // free, no stock

    for (int i = 0; i < n; i++) {
        int prevHold = hold;
        int prevSold = sold;
        hold = max(hold, rest - prices[i]);   // keep or buy today
        sold = prevHold + prices[i];          // sell today
        rest = max(rest, prevSold);           // rest or cooldown
    }
    return max(sold, rest);
}

int main(void) {
    int prices[] = {1, 2, 3, 0, 2};
    int n = 5;
    printf("%d\n", maxProfit(prices, n));
    return 0;
}

3

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int maxProfit(vector<int>& prices) {
    int hold = INT_MIN;   // own a stock
    int sold = 0;         // just sold today
    int rest = 0;         // free, no stock

    for (int price : prices) {
        int prevHold = hold;
        int prevSold = sold;
        hold = max(hold, rest - price);   // keep or buy today
        sold = prevHold + price;          // sell today
        rest = max(rest, prevSold);       // rest or cooldown
    }
    return max(sold, rest);
}

int main() {
    vector<int> prices = {1, 2, 3, 0, 2};
    cout << maxProfit(prices) << endl;
    return 0;
}

3

public class StockCooldown {
    public static int maxProfit(int[] prices) {
        int hold = Integer.MIN_VALUE;   // own a stock
        int sold = 0;                   // just sold today
        int rest = 0;                   // free, no stock

        for (int price : prices) {
            int prevHold = hold;
            int prevSold = sold;
            hold = Math.max(hold, rest - price);   // keep or buy
            sold = prevHold + price;               // sell today
            rest = Math.max(rest, prevSold);       // rest or cooldown
        }
        return Math.max(sold, rest);
    }

    public static void main(String[] args) {
        int[] prices = { 1, 2, 3, 0, 2 };
        System.out.println(maxProfit(prices));
    }
}

3

def max_profit(prices):
    hold = float("-inf")   # own a stock
    sold = 0               # just sold today
    rest = 0               # free, no stock

    for price in prices:
        prev_hold = hold
        prev_sold = sold
        hold = max(hold, rest - price)    # keep holding or buy today
        sold = prev_hold + price          # sell today
        rest = max(rest, prev_sold)       # rest or cooldown after a sale
    return max(sold, rest)


prices = [1, 2, 3, 0, 2]
print(max_profit(prices))

3

function maxProfit(prices) {
  let hold = -Infinity;   // own a stock
  let sold = 0;           // just sold today
  let rest = 0;           // free, no stock

  for (const price of prices) {
    const prevHold = hold;
    const prevSold = sold;
    hold = Math.max(hold, rest - price);   // keep or buy today
    sold = prevHold + price;               // sell today
    rest = Math.max(rest, prevSold);       // rest or cooldown
  }
  return Math.max(sold, rest);
}

const prices = [1, 2, 3, 0, 2];
console.log(maxProfit(prices));

3

Let us walk through the Python version line by line. The why behind each line is the state machine in action.

hold = float("-inf") starts the holding state as a huge negative number. Before any day, owning a stock is impossible, so we make it so bad it can never be chosen by mistake.

sold = 0 and rest = 0 start the other two states at zero profit. Doing nothing earns nothing, which is the right base.

for price in prices: steps through one day at a time. Each loop is one column of the imagined state grid.

prev_hold = hold and prev_sold = sold save yesterday’s values. We must freeze them, because the new sold and rest need the old numbers, not the just-updated ones.

hold = max(hold, rest - price) updates the hold state. Either you were already holding, or you buy today. Buying means starting from yesterday’s rest and paying the price, which is rest - price.

sold = prev_hold + price updates the sold state. To sell today you must have been holding yesterday, then you add today’s price as income.

rest = max(rest, prev_sold) updates the rest state. You either keep resting, or you arrive here by cooling down from yesterday’s sale. That cooldown is exactly the one-day rest the problem demands.

return max(sold, rest) gives the answer. Holding a stock at the very end is never the best, since unsold shares earn nothing. So the best is whichever of sold or rest is larger.

⏱️ Time and Space Complexity

Plain recursion is exponential, since it re-solves the same day and state again and again. Memoization brings it to O(n) time but uses O(n) memory for the table. The state machine tabulation is also O(n) time. The space-optimized version keeps just three numbers, so it uses O(1) memory while staying just as fast.

🧩 Key Takeaways

• ✅ Each day you are in one of three states: holding, just sold, or resting.
• ✅ The cooldown is captured by letting rest come only from yesterday’s sold.
• ✅ Today’s values depend only on yesterday’s, so three variables are enough.
• ✅ Freeze yesterday’s hold and sold before updating, or the math goes wrong.
• ✅ The final answer is the larger of sold and rest, never hold.

🚀 What’s Next?

• Coin Change 2
• Partition Equal Subset Sum