Best Time to Buy and Sell Stock with Cooldown

How it works

This problem follows the same idea as the previous dynamic programming solutions:
we want to maximize profit while respecting the cooldown rule (after selling, we must wait one day before buying again).

In the bottom-up DP approach, we only ever use values from the next day and the day after next. That means we do not need a full DP table — we can compress the state into a few variables.

Instead of storing results for every day, we keep track of:

• the best profit if we are allowed to buy on the next day
• the best profit if we are allowed to sell on the next day
• the best profit if we are allowed to buy two days ahead (needed for cooldown)

By updating these values while iterating backward, we achieve the same result using constant space.

Steps

1. Initialize variables to represent future DP states:
   • dp1_buy: profit if we can buy on the next day
   • dp1_sell: profit if we can sell on the next day
   • dp2_buy: profit if we can buy two days ahead (used after selling)
2. Traverse the prices array from the last day to the first day.
3. For each day:
   • Compute the best profit if we are allowed to buy:
     • either buy today (use next day’s sell profit minus price)
     • or skip today (keep next day’s buy profit)
   • Compute the best profit if we are allowed to sell:
     • either sell today (use profit from two days ahead plus price)
     • or skip today (keep next day’s sell profit)
4. Shift the state variables forward to represent the next iteration:
   • update dp2_buy
   • update dp1_buy and dp1_sell
5. After processing all days, dp1_buy represents the maximum profit starting from day 0 with permission to buy
6. Return dp1_buy

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Forgetting the Cooldown Day After Selling

After selling, you must skip one day before buying again. A common mistake is transitioning directly to the buying state on the next day instead of skipping to i + 2.

Confusing the Buying and Selling States

Mixing up which state allows buying versus selling leads to subtracting when you should add (or vice versa). When buying=True, you subtract the price; when buying=False, you add it.

Off-by-One Errors in Bottom-Up DP Bounds

When iterating backward and accessing dp[i + 2], forgetting to check bounds causes index out of range errors. The DP table needs size n + 2 or proper boundary checks.

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp1_buy, dp1_sell = 0, 0
        dp2_buy = 0

        for i in range(n - 1, -1, -1):
            dp_buy = max(dp1_sell - prices[i], dp1_buy)
            dp_sell = max(dp2_buy + prices[i], dp1_sell)
            dp2_buy = dp1_buy
            dp1_buy, dp1_sell = dp_buy, dp_sell

        return dp1_buy

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int dp1_buy = 0, dp1_sell = 0;
        int dp2_buy = 0;

        for (int i = n - 1; i >= 0; --i) {
            int dp_buy = max(dp1_sell - prices[i], dp1_buy);
            int dp_sell = max(dp2_buy + prices[i], dp1_sell);
            dp2_buy = dp1_buy;
            dp1_buy = dp_buy;
            dp1_sell = dp_sell;
        }

        return dp1_buy;
    }
};