Sponsored
Sponsored
This approach uses dynamic programming to track three states on each day: holding, not holding with cooldown, and not holding without cooldown. The idea is to decide the best action for any day based on the previous day's states. At each step, calculate the maximum profit for holding a stock, selling it, or being idle.
Time Complexity: O(n), where n is the number of days. Each day's prices are visited once.
Space Complexity: O(1), since only a fixed amount of extra space is used.
1class Solution:
2 def maxProfit(self, prices):
3 if not prices:
4 return 0
5 hold, sell, cooldown = -prices[0], 0, 0
6 for price in prices[1:]:
7 prev_sell = sell
8 sell = hold + price
9 hold = max(hold, cooldown - price)
10 cooldown = max(cooldown, prev_sell)
11 return max(sell, cooldown)
12
13if __name__ == '__main__':
14 sol = Solution()
15 prices = [1, 2, 3, 0, 2]
16 print("Max Profit:", sol.maxProfit(prices))This Python solution similarly uses dynamic programming to track three states. hold, sell, and cooldown are adjusted as we realize maximum profit. max function is used to determine the most profitable action each day.
This approach involves a recursive solution that tracks the profit by exploring all possible transactions. To optimize the solution, memoization is used to store and reuse results of repeated states to avoid redundant calculations.
Time Complexity: O(n), where n is the number of days. Thanks to memoization, each state is computed once.
Space Complexity: O(n), for the memoization table.
This Python implementation uses a dictionary for memoization and a recursive function solve that handles state transitions and profit calculations, thus efficiently determining maximum profit through stored results of previously computed states.