309. 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)

Example 1:

Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

Example 2:

Input: prices = [1]
Output: 0

Constraints:

• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000

Python Solution

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        
        n = len(prices)
        # hold[i]: max profit if we hold stock at day i
        # sold[i]: max profit if we sold stock at day i
        # rest[i]: max profit if we rest at day i
        hold = [0] * n
        sold = [0] * n
        rest = [0] * n
        
        # Initialize first day
        hold[0] = -prices[0]  # Buy stock
        
        for i in range(1, n):
            # If we hold stock at day i, either we held it from day i-1,
            # or we buy it after resting on day i-1
            hold[i] = max(hold[i-1], rest[i-1] - prices[i])
            
            # If we sold stock at day i, we must have held it at day i-1
            sold[i] = hold[i-1] + prices[i]
            
            # If we rest at day i, we take the max profit from either
            # resting or selling at day i-1
            rest[i] = max(rest[i-1], sold[i-1])
        
        # Return the max of the last day's sold or rest state
        return max(sold[n-1], rest[n-1])

Java Solution

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;
        
        int n = prices.length;
        int[] hold = new int[n];
        int[] sold = new int[n];
        int[] rest = new int[n];
        
        // Initialize first day
        hold[0] = -prices[0];
        
        for (int i = 1; i < n; i++) {
            hold[i] = Math.max(hold[i-1], rest[i-1] - prices[i]);
            sold[i] = hold[i-1] + prices[i];
            rest[i] = Math.max(rest[i-1], sold[i-1]);
        }
        
        return Math.max(sold[n-1], rest[n-1]);
    }
}

C++ Solution

class Solution {
public:
    int maxProfit(vector& prices) {
        if (prices.empty()) return 0;
        
        int n = prices.size();
        vector hold(n, 0);
        vector sold(n, 0);
        vector rest(n, 0);
        
        // Initialize first day
        hold[0] = -prices[0];
        
        for (int i = 1; i < n; i++) {
            hold[i] = max(hold[i-1], rest[i-1] - prices[i]);
            sold[i] = hold[i-1] + prices[i];
            rest[i] = max(rest[i-1], sold[i-1]);
        }
        
        return max(sold[n-1], rest[n-1]);
    }
};

JavaScript Solution

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if (!prices.length) return 0;
    
    const n = prices.length;
    const hold = new Array(n).fill(0);
    const sold = new Array(n).fill(0);
    const rest = new Array(n).fill(0);
    
    // Initialize first day
    hold[0] = -prices[0];
    
    for (let i = 1; i < n; i++) {
        hold[i] = Math.max(hold[i-1], rest[i-1] - prices[i]);
        sold[i] = hold[i-1] + prices[i];
        rest[i] = Math.max(rest[i-1], sold[i-1]);
    }
    
    return Math.max(sold[n-1], rest[n-1]);
};

C# Solution

public class Solution {
    public int MaxProfit(int[] prices) {
        if (prices == null || prices.Length <= 1) return 0;
        
        int n = prices.Length;
        int[] hold = new int[n];
        int[] sold = new int[n];
        int[] rest = new int[n];
        
        // Initialize first day
        hold[0] = -prices[0];
        
        for (int i = 1; i < n; i++) {
            hold[i] = Math.Max(hold[i-1], rest[i-1] - prices[i]);
            sold[i] = hold[i-1] + prices[i];
            rest[i] = Math.Max(rest[i-1], sold[i-1]);
        }
        
        return Math.Max(sold[n-1], rest[n-1]);
    }
}