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}C# implementation keeps the same control flow and algorithm as other languages, using an array to maintain profit evaluation for each potential stock transaction by iterating over possible transaction days.
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.