309. Best Time to Buy and Sell Stock with Cooldown
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
# Author: Huahua # Time complexity: O(n) # Space complexity: O(n) class Solution: def maxProfit(self, prices: List[int]) -> int: @cache def dp(i: int) -> Tuple[int, int, int]: """ Returns 1) sold: Max profit w/o holdings. Can't buy. Can't sell. 2) holding: Max profit w/ holdings. Can't buy, Can sell. 3) cooldown: Max profit w/o holdings. Can buy. Can't sell.""" if i < 0: return -10**9, -10**9, 0 sold, holding, cooldown = dp(i - 1) return (holding + prices[i], # sold max(holding, cooldown - prices[i]), # do nothing, or buy. max(cooldown, sold)) # cooldown return max(dp(len(prices) - 1)) |
714 Best Time to Buy and Sell Stock with Transaction Fee
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
# Author: Huahua # Time complexity: O(n) # Space complexity: O(n) class Solution: def maxProfit(self, prices: List[int], fee: int) -> int: @cache def dp(i: int) -> Tuple[int, int]: """ Returns: 1) sold: Max profit w/o holdings. 2) holding: Max profit w/ holdings.""" if i < 0: return 0, -10**9 sold, holding = dp(i - 1) return (max(sold, holding + prices[i] - fee), # do nothing, sell max(holding, sold - prices[i])) # do nothing, buy return dp(len(prices) - 1)[0] |