Published: Jul 27, 2022

## Problem Description

You are given an array

`prices`

where`prices[i]`

is the price of a given stock on the i-th 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).

Constraints:

`1 <= prices.length <= 5000`

`0 <= prices[i] <= 1000`

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

## Examples

```
Example 1:
Input: prices = [1,2,3,0,2]
Answer: 3
Explanation: 3 is the best profit which is from:
buy: index 0, sell: index 1, profit: 1
buy: index 3, sell: index 4, profit: 2
```

```
Example 2:
Input: prices = [1]
Answer: 0
Explanation: Stocks must be bought before selling those. There's no way to make profit.
```

## How to Solve

This is the fifth buy-sell-stock problem which has a slight variation to the basic one. In this problem, we need to hold a day after the stocks are sold. Aside of that, we can buy and sell as many times as we want. That being said, it looks similar to the buy and sell multiple times problem. That indicates the profit can be calculated by day-to-day difference. However, we should put the cooldown day before buying next. The solution here uses the idea of the dynamic programming such that: compare buying today or keep previous buy. Selling stocks is the same as buying. It compares selling today or keep previous sell.

## Solution

```
#include <vector>
using namespace std;
class BestTimeToBuyAndSellStockWithCooldown {
public:
int maxProfit(vector<int>& prices) {
int buy = INT_MIN, sell = 0, prev_buy = 0, prev_sell = 0;
for (auto price : prices)
{
prev_buy = buy;
buy = max(prev_buy, prev_sell - price);
prev_sell = sell;
sell = max(prev_sell, prev_buy + price);
}
return sell;
}
};
```

```
class BestTimeToBuyAndSellStockWithCooldown {
public int maxProfit(int[] prices) {
int buy = Integer.MIN_VALUE, sell = 0, prev_buy = 0, prev_sell = 0;
for (int price : prices) {
prev_buy = buy;
buy = Math.max(prev_buy, prev_sell - price);
prev_sell = sell;
sell = Math.max(prev_sell, prev_buy + price);
}
return sell;
}
}
```

```
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let buy = Number.MIN_SAFE_INTEGER, sell = 0, prev_buy = 0, prev_sell = 0;
for (let price of prices) {
prev_buy = buy
buy = Math.max(prev_buy, prev_sell - price)
prev_sell = sell
sell = Math.max(prev_sell, prev_buy + price)
}
return sell;
};
```

```
from typing import List
class BestTimeToBuyAndSellStockWithCooldown:
def maxProfit(self, prices: List[int]) -> int:
buy, sell, prev_buy, prev_sell = float('-inf'), 0, 0, 0
for price in prices:
prev_buy = buy
buy = max(prev_buy, prev_sell - price)
prev_sell = sell
sell = max(prev_sell, prev_buy + price)
return sell
```

```
# @param {Integer[]} prices
# @return {Integer}
def max_profit(prices)
buy = -5 * 10 ** 6 + 1; sell = 0; prev_buy = 0; prev_sell = 0;
prices.each do |price|
prev_buy = buy
buy = [prev_buy, prev_sell - price].max
prev_sell = sell
sell = [prev_sell, prev_buy + price].max
end
sell
end
```

## Complexities

- Time: O(n) – n: length of the input array.
- Space: O(1)