309. Best Time to Buy and Sell Stock with Cooldown

Description

You are given an array prices where prices[i] is the price of a stock on the ith day. You can decide each day whether to buy, sell, or skip. However, after you sell a stock, you cannot buy again the next day due to a cooldown period of 1 day. Your task is to find the maximum profit you can achieve. You can hold at most one share of stock at a time.

Intuition

The key idea is to use dynamic programming to track the maximum profit at each day based on two possible states:

• When you are holding a stock.
• When you are not holding a stock.

If you are holding a stock, you can either sell it and enter a cooldown period, or hold it until a future date. If you are not holding a stock, you can either buy a stock or skip the day. The cooldown period prevents consecutive buying and selling, which creates dependencies between days. This makes the problem well-suited for dynamic programming.

Approach

1. State Definition: - Define two arrays: - dpb[i]: Maximum profit if you buy/hold stock on the ith day. - dps[i]: Maximum profit if you sell stock on the ith day.
2. Recursive Transition: - If you are not holding a stock, you can: - Buy stock on day i and move to the next day holding the stock. The cost would be subtracted from your profit. - Skip buying on day i and check the maximum profit for day i+1. - If you are holding a stock, you can: - Sell the stock on day i, add the profit from selling, and move to day i+2 (due to the cooldown). - Skip selling on day i and move to the next day.
3. Base Case: - If you exceed the length of the price array, the profit is zero because no more transactions can be made.
4. Memoization: - Use two arrays dpb and dps to store intermediate results, preventing recalculations of the same subproblem.
5. Final Answer: - The result will be in dpb[0], representing the maximum profit you can make starting from day 0.

Complexity

Time Complexity:

• The time complexity is (O(n)), where (n) is the length of the prices array. This is because each day is processed once, and for each day, we decide whether to buy, sell, or skip, with all operations taking constant time.

Space Complexity:

• The space complexity is (O(n)), where (n) is the length of the prices array. This is due to the dpb and dps arrays, which store results for each day.

Code

C++

class Solution {
public:
    int maxProfit(std::vector& prices) {
        int n = prices.size();
        std::vector dpb(n, 0), dps(n, 0);

        std::function dfs = [&](int i, int stockPrice) -> int {
            if (i >= n)
                return 0;

            if (stockPrice == -1 && dpb[i])
                return dpb[i];
            if (stockPrice != -1 && dps[i])
                return dps[i];

            int price = prices[i];
            int skip = dfs(i + 1, stockPrice);

            if (stockPrice != -1) {
                int sell = price + dfs(i + 2, -1);
                dps[i] = std::max(skip, sell);
                return dps[i];
            } else {
                int buy = dfs(i + 1, price) - price;
                dpb[i] = std::max(buy, skip);
                return dpb[i];
            }
        };

        dfs(0, -1);
        return dpb[0];
    }
};

Python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dpb = [0] * n
        dps = [0] * n

        def dfs(i, stockPrice):
            if i >= n:
                return 0

            if stockPrice is None and dpb[i]:
                return dpb[i]
            if stockPrice is not None and dps[i]:
                return dps[i]

            price = prices[i]
            skip = dfs(i + 1, stockPrice)

            if stockPrice is not None:
                sell = price + dfs(i + 2, None)
                dps[i] = max(skip, sell)
                return dps[i]
            else:
                buy = dfs(i + 1, price) - price
                dpb[i] = max(buy, skip)
                return dpb[i]

        dfs(0, None)
        return dpb[0]

Java

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] dpb = new int[n];  // dp for buy state
        int[] dps = new int[n];  // dp for sell state
        Arrays.fill(dpb, -1);    // Initialize with -1 (unvisited)
        Arrays.fill(dps, -1);    // Initialize with -1 (unvisited)

        return dfs(prices, dpb, dps, 0, null);
    }

    private int dfs(int[] prices, int[] dpb, int[] dps, int i, Integer stockPrice) {
        if (i >= prices.length) {
            return 0;
        }

        if (stockPrice == null && dpb[i] != -1) {  // If we haven't bought a stock yet
            return dpb[i];
        }
        if (stockPrice != null && dps[i] != -1) {  // If we have already bought a stock
            return dps[i];
        }

        int price = prices[i];
        int skip = dfs(prices, dpb, dps, i + 1, stockPrice);  // Skip this day

        if (stockPrice != null) {  // If holding a stock, we can sell
            int sell = price + dfs(prices, dpb, dps, i + 2, null);  // Sell and go to i + 2 because of cooldown
            dps[i] = Math.max(skip, sell);
            return dps[i];
        } else {  // If not holding a stock, we can buy
            int buy = dfs(prices, dpb, dps, i + 1, price) - price;  // Buy and hold stock
            dpb[i] = Math.max(buy, skip);
            return dpb[i];
        }
    }
}

JavaScript

var maxProfit = function(prices) {

    let res = 0;
    const dpb = [];
    const dps = [];

    function dfs(i, stockPrice) {

        if (i >= prices.length) {
            return 0;
        }

        if (stockPrice === undefined && dpb[i]) {
            return dpb[i];
        } 

        if (stockPrice !== undefined && dps[i]) {
            return dps[i];
        } 

        const price = prices[i];
        const skip = dfs(i + 1, stockPrice);

        if (stockPrice !== undefined) {
            // let newProfit += price;
            const sell = price + dfs(i + 2, undefined);
            dps[i] = Math.max(skip, sell);

            return dps[i];

        } else {
            const buy = dfs(i + 1, price) - price;
            dpb[i] = Math.max(buy, skip);

            return dpb[i];
        }
    }
    dfs(0, undefined);

    return dpb[0];
};