1014. Best Sightseeing Pair
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
# Author: Huahua # Time complexity: O(n) # Space complexity: O(n) class Solution: def maxScoreSightseeingPair(self, values: List[int]) -> int: # score = (values[i] + i) + (values[j] - j) @cache def dp(j: int) -> Tuple[int, int]: """Returns: 1) Max score of values[0..j] 2) Largest values[i] + i (i <= j).""" if j < 0: return 0, 0 s, v = dp(j - 1) return max(s, v + values[j] - j), max(v, values[j] + j) return dp(len(values) - 1)[0] |
121. Best Time to Buy and Sell Stock
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
# 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]: """Returns: 1) max profit of prices[0:i]. 2) min price of prices[0:i].""" if i < 0: return 0, 10**9 max_profit, min_price = dp(i - 1) return max(max_profit, prices[i] - min_price), min(min_price, prices[i]) return dp(len(prices) - 1)[0] |
122. Best Time to Buy and Sell Stock II
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
# 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]: """Returns: 1) Max profit after i-th day. Holding no stocks. Can buy. 2) Max balance after i-th day. Holding a stock. Can sell. """ if i < 0: return 0, -10**9 profit, balance = dp(i - 1) return (max(profit, balance + prices[i]), # do nothing, sell max(balance, profit - prices[i])) # do nothing, buy return dp(len(prices) - 1)[0] |