# 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; }