Solution For Best Time To Buy And Sell Stock With Cooldown

The Best Time to Buy and Sell Stock with Cooldown problem on LeetCode is a dynamic programming problem where the goal is to maximize the profit of a given stock with a one-day cooldown period.

Problem statement:

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day to sell that stock.

You are also given a cooldown period of one day, i.e., no transactions can be made on the next day after a sell.

Return the maximum profit you can achieve.

Solution:

To solve this problem, we can use dynamic programming to keep track of the maximum profit we can make on each day.

We will create two arrays:

1) buy[i] – the maximum profit we can make by buying the stock on day i
2) sell[i] – the maximum profit we can make by selling the stock on day i

We can compute the buy and sell arrays using the following recurrence relation:

buy[i] = max(sell[i-2] – prices[i], buy[i-1])
sell[i] = max(buy[i-1] + prices[i], sell[i-1])

The buy array keeps track of the maximum profit we can make by buying the stock on day i.

To compute buy[i], we have two options:

1) Not buy the stock on day i and carry forward the maximum profit from the previous day, buy[i-1].
2) Buy the stock on day i by subtracting the price of the stock on day i, prices[i], from the maximum profit we can make by selling the stock on day i-2, sell[i-2].

The sell array keeps track of the maximum profit we can make by selling the stock on day i.

To compute sell[i], we have two options:

1) Not sell the stock on day i and carry forward the maximum profit from the previous day, sell[i-1].
2) Sell the stock on day i by adding the price of the stock on day i, prices[i], to the maximum profit we can make by buying the stock on day i-1, buy[i-1].

We will return sell[n-1], where n is the length of the prices array, as it will give us the maximum profit we can make by selling the stock on the last day.

Code:

Here is the Python code to solve this problem:

def maxProfit(prices: List[int]) -> int:
n = len(prices)
if n < 2:
return 0
buy = [0] * n
sell = [0] * n
buy[0] = -prices[0] for i in range(1, n):
buy[i] = max(sell[i-2] – prices[i], buy[i-1])
sell[i] = max(buy[i-1] + prices[i], sell[i-1])
return sell[n-1]

Time complexity:

The time complexity of this solution is O(n), where n is the length of the prices array, as we only need to loop through the array once to calculate the buy and sell arrays.

Space complexity:

The space complexity of this solution is O(n), as we are storing two arrays buy and sell of length n.

Step by Step Implementation For Best Time To Buy And Sell Stock With Cooldown

class Solution {
    public int maxProfit(int[] prices) {
        //This is a classic dynamic programming problem. 
        //We define dp[i] to be the maximum profit we can make by the end of day i
        //We can then write our recurrence as: 
        //dp[i] = max(dp[i-1], prices[i] - prices[j] + dp[j-2]), j <= i-1
        //This says that the maximum profit we can make by the end of day i is either the maximum profit we made by the end of day i-1, 
        //or the maximum profit we made by selling on day i-1 and buying on day j, plus the maximum profit we made by the end of day j-2. 
        //The reason we have j-2 and not j-1 is because we are not allowed to buy on the same day we sell, so we must wait one day in between. 
        
        if (prices.length == 0) return 0;
        int dp[] = new int[prices.length];
        dp[0] = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i] = Math.max(dp[i-1], prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        return dp[prices.length - 1];
    }
}

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # Base cases
        if len(prices) <= 1:
            return 0
        
        # Initialize dp array
        # dp[i][0] represents the maximum profit we can make from days [0, i]
        # and not being in a "cool down" period
        # dp[i][1] represents the maximum profit we can make from days [0, i]
        # and being in a "cool down" period
        dp = [[0 for _ in range(2)] for _ in range(len(prices))]
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        
        # Fill in dp array
        for i in range(1, len(prices)):
            # On day i, we have two options:
            # 1) Sell our stock and enter cool down period
            # 2) Do nothing
            # Option 1 gives us the profit from days [0, i-2] plus the 
            # current profit, which is prices[i] - prices[i-1].
            # Option 2 gives us the profit from days [0, i-1], which is
            # simply dp[i-1][0].
            # We take the maximum of the two options.
            dp[i][0] = max(dp[i-2][0] + prices[i] - prices[i-1], dp[i-1][0])
            # On day i, we have two options:
            # 1) Buy a stock
            # 2) Do nothing
            # Option 1 gives us the profit from days [0, i-1] minus the
            # current price.
            # Option 2 gives us the profit from days [0, i-1], which is
            # simply dp[i-1][1].
            # We take the maximum of the two options.
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
            
        # Return the maximum profit from days [0, len(prices) - 1] not being
        # in a "cool down" period. This is simply dp[len(prices) - 1][0].
        return dp[len(prices) - 1][0]

var maxProfit = function(prices) {
    let buy = sell = rest = 0;
    
    for (let i = 0; i < prices.length; i++) {
        let prev_buy = buy;
        let prev_sell = sell;
        let prev_rest = rest;
        
        // buy
        buy = Math.max(prev_rest - prices[i], prev_buy);
        
        // sell
        sell = Math.max(prev_buy + prices[i], prev_sell);
        
        // rest
        rest = Math.max(prev_sell, prev_rest);
    }
    
    return Math.max(sell, rest);
};

class Solution {
public:
    int maxProfit(vector& prices) {
        int n = prices.size();
        if (n == 0) return 0;
        vector buy(n, 0);
        vector sell(n, 0);
        vector rest(n, 0);
        buy[0] = -prices[0];
        for (int i = 1; i < n; ++i) {
            buy[i] = max(buy[i-1], rest[i-1] - prices[i]);
            sell[i] = max(sell[i-1], buy[i-1] + prices[i]);
            rest[i] = max(rest[i-1], sell[i-1]);
        }
        return max(sell[n-1], rest[n-1]);
    }
};

public int MaxProfit(int[] prices) { int sell = 0, prev_sell = 0, buy = Int32.MinValue, prev_buy; for (int i = 0; i < prices.Length; i++) { prev_buy = buy; buy = Math.Max(prev_sell - prices[i], prev_buy); prev_sell = sell; sell = Math.Max(prev_buy + prices[i], prev_sell); } return sell; }