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.
1public class Solution {
2 public int maxProfit(int k, int[] prices) {
3 int n = prices.length;
4 if (n == 0) return 0;
5 if (k >= n / 2) {
6 int profit = 0;
7 for (int i = 1; i < n; i++)
8 profit += Math.max(0, prices[i] - prices[i - 1]);
9 return profit;
10 }
11 int[] profits = new int[n];
12 for (int j = 0; j < k; j++) {
13 int maxDiff = -prices[0];
14 int prevProfit = 0;
15 for (int i = 1; i < n; i++) {
16 int temp = profits[i];
17 profits[i] = Math.max(profits[i - 1], prices[i] + maxDiff);
18 maxDiff = Math.max(maxDiff, prevProfit - prices[i]);
19 prevProfit = temp;
20 }
21 }
22 return profits[n - 1];
23 }
24}The Java implementation follows the same logic as the Python and C++ codes with adjustment to Java syntax. We use an array to update profit possibilities, using previous profits and maximum price differences.
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.
1#include <stdlib.h>
2#include <string.h>
We use malloc to create a 2D array for storing profit states. The approach involves calculating maximum difference adjustments each time a potential transaction point is evaluated, allowing a full exploration of transaction possibilities up to k times.