best_time_to_buy_and_sell_stock_with_cooldown
1from functools import cache 2 3 4# @leet start 5class Solution: 6 def maxProfit(self, prices: list[int]) -> int: 7 """ 8 This question asks us to calculate the max profit for buying + selling 9 as many stocks as we want, given a 1 day cooldown after selling a stock. 10 11 Therefore, on any given day, there are 3 choices you have: 12 1. Do nothing (pass) 13 2. Buy (where you want to minimize the current minimum price seen) 14 3. Sell (where you want to maximize the profit by buying the stock at 15 the minimum you've seen so far, and selling it at the current price, 16 and applying the cooldown rule) 17 18 We can translate those rules into a function and then cache its results. 19 """ 20 21 @cache 22 def traverse(i, curr_min, curr_max): 23 if i >= len(prices): 24 return 0 25 curr_min = min(curr_min, prices[i]) 26 curr_max = max(curr_max, prices[i]) 27 buy = traverse(i + 1, curr_min, curr_max) 28 sell = prices[i] - curr_min + traverse(i + 2, float("inf"), float("-inf")) 29 return max(buy, sell) 30 31 return traverse(0, float("inf"), float("-inf")) 32 33 34# @leet end 35 36 37def test(): 38 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def maxProfit(self, prices: list[int]) -> int: 8 """ 9 This question asks us to calculate the max profit for buying + selling 10 as many stocks as we want, given a 1 day cooldown after selling a stock. 11 12 Therefore, on any given day, there are 3 choices you have: 13 1. Do nothing (pass) 14 2. Buy (where you want to minimize the current minimum price seen) 15 3. Sell (where you want to maximize the profit by buying the stock at 16 the minimum you've seen so far, and selling it at the current price, 17 and applying the cooldown rule) 18 19 We can translate those rules into a function and then cache its results. 20 """ 21 22 @cache 23 def traverse(i, curr_min, curr_max): 24 if i >= len(prices): 25 return 0 26 curr_min = min(curr_min, prices[i]) 27 curr_max = max(curr_max, prices[i]) 28 buy = traverse(i + 1, curr_min, curr_max) 29 sell = prices[i] - curr_min + traverse(i + 2, float("inf"), float("-inf")) 30 return max(buy, sell) 31 32 return traverse(0, float("inf"), float("-inf"))
def
maxProfit(self, prices: list[int]) -> int:
7 def maxProfit(self, prices: list[int]) -> int: 8 """ 9 This question asks us to calculate the max profit for buying + selling 10 as many stocks as we want, given a 1 day cooldown after selling a stock. 11 12 Therefore, on any given day, there are 3 choices you have: 13 1. Do nothing (pass) 14 2. Buy (where you want to minimize the current minimum price seen) 15 3. Sell (where you want to maximize the profit by buying the stock at 16 the minimum you've seen so far, and selling it at the current price, 17 and applying the cooldown rule) 18 19 We can translate those rules into a function and then cache its results. 20 """ 21 22 @cache 23 def traverse(i, curr_min, curr_max): 24 if i >= len(prices): 25 return 0 26 curr_min = min(curr_min, prices[i]) 27 curr_max = max(curr_max, prices[i]) 28 buy = traverse(i + 1, curr_min, curr_max) 29 sell = prices[i] - curr_min + traverse(i + 2, float("inf"), float("-inf")) 30 return max(buy, sell) 31 32 return traverse(0, float("inf"), float("-inf"))
This question asks us to calculate the max profit for buying + selling as many stocks as we want, given a 1 day cooldown after selling a stock.
Therefore, on any given day, there are 3 choices you have:
- Do nothing (pass)
- Buy (where you want to minimize the current minimum price seen)
- Sell (where you want to maximize the profit by buying the stock at the minimum you've seen so far, and selling it at the current price, and applying the cooldown rule)
We can translate those rules into a function and then cache its results.
def
test():