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 alllen(prices) == 1
, answer is0
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 attime = 0
and sell attime = 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 ofprices[i]
right now, and set thestock = 1
- sell: if the
stock = 1
previously, we can sell it for a profit ofprices[i]
and skip the next time step - hold: do nothing, just look at the next index.
- buy: if
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)
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Reverse integer | InterviewBit | LeetCode | Solution Explained
January 24, 2022