# Best Time to Buy and Sell Stock with Cooldown | Solution Explained

LeetCode 309. Best Time to Buy and Sell Stock with Cooldown. I solve this problem using recursion. Solution explained in detail. Problem Link.

## Problem Discussion

We are given the input as an array, and we have to return the maximum profit possible.

The solution:

As other people have pointed out, it can feel like a hard level problem. However, I have an explanation for Best Time to Buy and Sell Stock that you’ll love.

## Observations

As always, whenever confused, I suggest to look at a couple of basic examples, and see if you can find things out.

• `prices = [1]`, answer = `0`. The only operation is hold at this point, since you can never sell. For all `len(prices) == 1`, answer is `0`
• `prices = [1,2]`, answer = `1`. In this case, we can either hold out the entire time and get a profit of 0, or, we can buy at `time = 0` and sell at `time = 1` getting us a profit of 1.
• `prices = [1,2,3]`, answer = `2`. This is where things get more interesting. In this case, we somehow need the information of holding out at time = 1 instant. We want to look into the future, saying that perhaps we should wait for the stock price to increase.

Thus, we realize that we want to look into the future. If you have been following me, you know its the cue for recursion.

## Recursion

• return type: Its clear that we want the recursion to tell us what the profits are, since that is the goal.
• base case: the recursion ends when time/index >= n, the length of the array
• inputs to recursion: index & stock
• index: tells us what time it is right now
• stock: a binary 0/1 telling us the amount of stock we have
• to look into the future, we have 3 cases
• buy: if `stock = 0`, take the cost of `prices[i]` right now, and set the `stock = 1`
• sell: if the `stock = 1` previously, we can sell it for a profit of `prices[i]` and skip the next time step
• hold: do nothing, just look at the next index.

## Best Time to Buy and Sell Stock with Cooldown: Code

```class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 1: return 0

@lru_cache(None)
def recurse(i, stock):
if i >= n: return 0

buy = (-prices[i] + recurse(i+1, 1)) if stock == 0 else -inf
sell = (prices[i] + recurse(i+2, 0)) if stock == 1 else -inf
hold = recurse(i+1, stock)
return max(buy, sell, hold)

n = len(prices)
return recurse(0, 0)
```

## Best Time to Buy and Sell Stock with Cooldown: Code (Without LRU Cache)

```class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 1: return 0

def recurse(i, stock):
if i >= n: return 0

if dp[i][stock] != -inf: return dp[i][stock] # line added

buy = (-prices[i] + recurse(i+1, 1)) if stock == 0 else -inf
sell = (prices[i] + recurse(i+2, 0)) if stock == 1 else -inf
hold = 0 + recurse(i+1, stock)

dp[i][stock] = max(buy, sell, hold) # line added
return dp[i][stock]

n = len(prices)
dp = [[-inf, -inf] for _ in range(n+1)] # initializing dp
return recurse(0, 0)
```
##### Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Disjoint Intervals | InterviewBit | Solution Explained

June 12, 2022

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022

This site uses Akismet to reduce spam. Learn how your comment data is processed.