Problem Statement
leetcode problem link
Memoization [Accepted]
class Solution:
def maxProfit(self, prices: List[int]) -> int:
@cache
def dp(i, is_holding, is_cooldown):
if i == len(prices):
return 0
ans = dp(i + 1, is_holding, False)
if not is_cooldown:
if is_holding:
ans = max(ans, dp(i + 1, False, True) + prices[i])
else:
ans = max(ans, dp(i + 1, True, False) - prices[i])
return ans
return dp(0, False, False)
Editorial
Approach 1: Dynamic Programming with State Machine
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
sold, held, reset = float('-inf'), float('-inf'), 0
for price in prices:
# Alternative: the calculation is done in parallel.
# Therefore no need to keep temporary variables
#sold, held, reset = held + price, max(held, reset-price), max(reset, sold)
pre_sold = sold
sold = held + price
held = max(held, reset - price)
reset = max(reset, pre_sold)
return max(sold, reset)
Approach 2: Yet-Another Dynamic Programming
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
L = len(prices)
# padding the array with additional zero to simply the logic
MP = [0] * (L + 2)
for i in range(L-1, -1, -1):
C1 = 0
# Case 1). buy and sell the stock
for sell in range(i + 1, L):
profit = (prices[sell] - prices[i]) + MP[sell + 2]
C1 = max(profit, C1)
# Case 2). do no transaction with the stock p[i]
C2 = MP[i + 1]
# sum up two cases
MP[i] = max(C1, C2)
return MP[0]