# 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:

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
sell = [0] * n
buy[0] = -prices[0] for i in range(1, n):
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:
# 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_sell = sell;
let prev_rest = rest;

// 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 sell(n, 0);
vector rest(n, 0);
for (int i = 1; i < n; ++i) {
`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; }`