Sponsored
Sponsored
This approach involves using a dynamic programming table where dp[i][j] represents the maximum profit obtainable on the ith day with up to j transactions. The state can be compressed by keeping track of two main variables: one for the max profit holding deals and one for not holding deals.
Time Complexity: O(kn), where n is the number of days and k is the number of allowed transactions.
Space Complexity: O(n), as we are storing profit states for each day.
1def maxProfit(k, prices):
2 if not prices:
3 return 0
4 n = len(prices)
5 if k >= n // 2:
6 return sum(max(prices[i] - prices[i - 1], 0) for i in range(1, n))
7 profits = [0] * n
8 for j in range(k):
9 prev_profit = 0
10 max_diff = -prices[0]
11 for i in range(1, n):
12 temp = profits[i]
13 profits[i] = max(profits[i - 1], prices[i] + max_diff)
14 max_diff = max(max_diff, prev_profit - prices[i])
15 prev_profit = temp
16 return profits[-1]We initiate with a check for empty prices array and then determine if we are allowed more transactions than needed for continuous buying and selling. If not, proceed with a reduced number of dynamic programming states constrained by the number of transactions. We update profits using previous profits and manage maximum price differences dynamically.
This method is a classical dynamic programming solution where we maintain a 2D array dp[j][i], that contains the maximum profit achievable having executed up to j transactions on the ith day.
Time Complexity: O(kn).
Space Complexity: O(kn), uses additional space for the DP table.
1function maxProfit(k, prices) {
2 ifUtilizes a 2D array dynamically allocated for handling transaction evaluations, updating them continuously using previous transaction values and price differences for optimal profit assessment.