Best Time to Buy and Sell Stock with Cooldown

Problem Description

You are given an array prices where prices[i] is the price of a given stock on the ith 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 restrictions:

• After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Examples

Constraints

• 1 ≤ prices.length ≤ 5000
• 0 ≤ prices[i] ≤ 1000

State Machine DP

On any day i, we can be in one of three states:

1. held: we currently hold a share of stock.
2. sold: we just sold a share of stock on day i.
3. reset: we do not hold stock, and we did not sell stock today (cooldown or inactive).

Transitions:

• held[i] = max(held[i-1], reset[i-1] - price) (either keep holding, or buy today using capital from a previous cooldown/reset state).
• sold[i] = held[i-1] + price (sell the stock today).
• reset[i] = max(reset[i-1], sold[i-1]) (either stay inactive, or transition from yesterday’s sold/cooldown state).

Initialize:

• held = -infinity
• sold = 0
• reset = 0

Because the states for day i only depend on the values from day i-1, we can optimize the space to O(1) by maintaining only three variables.

Solution: State Machine Transition (O(1) Space)

class Solution {
    public int maxProfit(int[] prices) {
        int held = Integer.MIN_VALUE;
        int sold = 0;
        int reset = 0;

        for (int price : prices) {
            int prevHeld = held;
            int prevSold = sold;
            int prevReset = reset;

            held = Math.max(prevHeld, prevReset - price);
            sold = prevHeld + price;
            reset = Math.max(prevReset, prevSold);
        }

        return Math.max(sold, reset);
    }
}

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        held = float('-inf')
        sold = 0
        reset = 0

        for price in prices:
            prev_held = held
            prev_sold = sold
            prev_reset = reset

            held = max(prev_held, prev_reset - price)
            sold = prev_held + price
            reset = max(prev_reset, prev_sold)

        return max(sold, reset)

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxProfit(std::vector<int>& prices) {
        int held = -1e9;
        int sold = 0;
        int reset = 0;

        for (int price : prices) {
            int prevHeld = held;
            int prevSold = sold;
            int prevReset = reset;

            held = std::max(prevHeld, prevReset - price);
            sold = prevHeld + price;
            reset = std::max(prevReset, prevSold);
        }

        return std::max(sold, reset);
    }
};

Complexity Analysis:

• Time Complexity: O(N) where N is the length of prices. We make a single pass over the prices.
• Space Complexity: O(1) auxiliary space.

← All Problems