Intuition
Complexity
Runtime
Space
Code
Bottom Up
Top Down
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
@cache
def r(i, bought_price):
if i >= n:
return 0
# held previously
if bought_price != -1:
profit = prices[i] - bought_price
# sell and hold vs hold
return max(profit + r(i + 2, -1), r(i + 1, bought_price))
# buy or don't buy
return max(r(i + 1, prices[i]), r(i + 1, -1))
return r(0, -1)Without Cache
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = {}
def r(i, bought_price):
if i >= n:
return 0
if (i, bought_price) in dp:
return dp[(i, bought_price)]
# held previously
if bought_price != -1:
profit = prices[i] - bought_price
# sell and hold vs hold
dp[(i, bought_price)] = max(profit + r(i + 2, -1), r(i + 1, bought_price))
else:
# buy or don't buy
dp[(i, bought_price)] = max(r(i + 1, prices[i]), r(i + 1, -1))
return dp[(i, bought_price)]
return r(0, -1)Notes
Cards
START Basic Front: Best Time To Buy And Sell Stock With Cooldown Back: END