309. Best Time to Buy and Sell Stock with Cooldown – Leetcode Solutions

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

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        
        # Number of days in the price list
        n = len(prices)
        
        # Create three arrays to keep track of the states on each day:
        # buy[i] - the maximum profit we can have on day i if the last action we did was a buy
        # sell[i] - the maximum profit we can have on day i if the last action we did was a sell
        # cooldown[i] - the maximum profit we can have on day i if we are in a cooldown period (i.e., no action)
        
        buy = [0] * n
        sell = [0] * n
        cooldown = [0] * n
        
        # Initial conditions: on day 0, we can only buy or do nothing.
        # If we buy on the first day, the profit is -prices[0] (negative, because we're spending money)
        buy[0] = -prices[0]
        sell[0] = 0
        cooldown[0] = 0
        
        # Iterate over each day starting from day 1
        for i in range(1, n):
            # buy[i] is the maximum of:
            # - We keep the same 'buy' state from the previous day (i.e., no transaction)
            # - We transition from cooldown and buy on the current day (i.e., we bought today)
            buy[i] = max(buy[i - 1], cooldown[i - 1] - prices[i])
            
            # sell[i] is the maximum of:
            # - We sell today, so we take the best possible state from 'buy[i-1]' and add today's price
            sell[i] = buy[i - 1] + prices[i]
            
            # cooldown[i] is the maximum of:
            # - We stay in cooldown from the previous day
            # - We just sold today, so we enter cooldown tomorrow (but take the profit from 'sell[i]')
            cooldown[i] = max(cooldown[i - 1], sell[i - 1])
        
        # The maximum profit will be the maximum of selling or cooling down on the last day,
        # because we can't be holding any stock on the last day to maximize profit.
        return max(sell[-1], cooldown[-1])

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // If there are no prices, no profit can be made
        if (prices.empty()) {
            return 0;
        }

        // Number of days in the price list
        int n = prices.size();
        
        // Create three arrays to keep track of the states on each day:
        // buy[i] - the maximum profit we can have on day i if the last action was a buy
        // sell[i] - the maximum profit we can have on day i if the last action was a sell
        // cooldown[i] - the maximum profit we can have on day i if we are in a cooldown period (i.e., no action)
        vector<int> buy(n, 0);
        vector<int> sell(n, 0);
        vector<int> cooldown(n, 0);
        
        // Initial conditions:
        // On day 0, if we buy, the profit is -prices[0] (we are spending money)
        // We cannot sell on the first day, so sell[0] is 0
        // On the first day, cooldown is also 0 as no transactions can happen before day 0
        buy[0] = -prices[0];
        sell[0] = 0;
        cooldown[0] = 0;
        
        // Iterate over each day starting from day 1
        for (int i = 1; i < n; ++i) {
            // buy[i] is the maximum of:
            // - Not buying today and carrying forward the buy state from yesterday (buy[i-1])
            // - Buying today (only possible after a cooldown period), so we transition from cooldown to buy
            buy[i] = max(buy[i - 1], cooldown[i - 1] - prices[i]);
            
            // sell[i] is the maximum of:
            // - Selling today, meaning we take the profit from buying on a previous day and add today's price
            sell[i] = buy[i - 1] + prices[i];
            
            // cooldown[i] is the maximum of:
            // - Staying in cooldown, which means carrying forward cooldown from the previous day
            // - Selling yesterday, which forces a cooldown today
            cooldown[i] = max(cooldown[i - 1], sell[i - 1]);
        }
        
        // The maximum profit will be the maximum of selling or being in cooldown on the last day
        // We can't end the last day holding stock (i.e., in buy state), so we don't consider buy[n-1]
        return max(sell[n - 1], cooldown[n - 1]);
    }
};

var maxProfit = function(prices) {
    // If there are no prices or only one day, no transactions can be made
    if (prices.length === 0) {
        return 0;
    }

    // Number of days in the price list
    const n = prices.length;

    // Create three arrays to store the maximum profit for each state at each day:
    // - buy[i]: max profit on day i if the last action was a buy
    // - sell[i]: max profit on day i if the last action was a sell
    // - cooldown[i]: max profit on day i if in a cooldown period (no action taken on day i)
    let buy = new Array(n).fill(0);
    let sell = new Array(n).fill(0);
    let cooldown = new Array(n).fill(0);

    // Initial conditions: on day 0
    // - buy[0] means we bought on the first day, so the profit is -prices[0]
    // - sell[0] is 0 because we can't sell on the first day without buying
    // - cooldown[0] is also 0 since no transactions can happen before day 0
    buy[0] = -prices[0];
    sell[0] = 0;
    cooldown[0] = 0;

    // Iterate through each day starting from day 1
    for (let i = 1; i < n; i++) {
        // On day i:
        // - We can either keep the buy from previous day or buy today (after a cooldown on day i-1)
        buy[i] = Math.max(buy[i - 1], cooldown[i - 1] - prices[i]);

        // - We can sell today (which requires that we had bought stock previously)
        sell[i] = buy[i - 1] + prices[i];

        // - We can be in cooldown, either from the previous day or because we sold on day i-1
        cooldown[i] = Math.max(cooldown[i - 1], sell[i - 1]);
    }

    // The maximum profit will be either from selling stock or being in cooldown on the last day
    // We cannot end in the "buy" state on the last day because that means we're holding stock
    return Math.max(sell[n - 1], cooldown[n - 1]);
};

class Solution {
    public int maxProfit(int[] prices) {
        // If the prices array is empty, no transactions can be made
        if (prices.length == 0) {
            return 0;
        }

        // Number of days
        int n = prices.length;

        // Arrays to store the maximum profit in each of the three states:
        // buy[i]: the maximum profit we can have on day i if the last action was a buy
        // sell[i]: the maximum profit we can have on day i if the last action was a sell
        // cooldown[i]: the maximum profit we can have on day i if we are in a cooldown period
        int[] buy = new int[n];
        int[] sell = new int[n];
        int[] cooldown = new int[n];

        // Initial conditions:
        // On day 0, if we buy, the profit is -prices[0] (since we're spending money).
        // We cannot sell on day 0, so sell[0] is 0.
        // cooldown[0] is also 0 as no transaction can happen before day 0.
        buy[0] = -prices[0];
        sell[0] = 0;
        cooldown[0] = 0;

        // Iterate over each day starting from day 1
        for (int i = 1; i < n; i++) {
            // On day i:
            // - Either we carry forward the buy from the previous day (buy[i-1]),
            //   or we buy today after being in a cooldown state on the previous day (cooldown[i-1] - prices[i])
            buy[i] = Math.max(buy[i - 1], cooldown[i - 1] - prices[i]);

            // - We sell today, which adds today's price to the profit we had after the last buy (buy[i-1] + prices[i])
            sell[i] = buy[i - 1] + prices[i];

            // - Either we stay in cooldown from the previous day (cooldown[i-1]),
            //   or we just sold yesterday, so we enter cooldown today (sell[i-1])
            cooldown[i] = Math.max(cooldown[i - 1], sell[i - 1]);
        }

        // The maximum profit on the last day will either come from selling or being in cooldown.
        // We cannot be in the 'buy' state on the last day, as that would mean holding stock.
        return Math.max(sell[n - 1], cooldown[n - 1]);
    }
}