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.
1#include <vector>
2#include <iostream>
3using namespace std;
4
5int maxProfit(int k, vector<int>& prices) {
6 int n = prices.size();
7 if (prices.empty()) return 0;
8 if (k >= n / 2) {
9 int total_profit = 0;
10 for (int i = 1; i < n; i++)
11 total_profit += max(0, prices[i] - prices[i - 1]);
12 return total_profit;
13 }
14 vector<int> profits(n, 0);
15 for (int j = 0; j < k; j++) {
16 int prev_profit = 0, max_diff = -prices[0];
17 for (int i = 1; i < n; i++) {
18 int temp = profits[i];
19 profits[i] = max(profits[i - 1], prices[i] + max_diff);
20 max_diff = max(max_diff, prev_profit - prices[i]);
21 prev_profit = temp;
22 }
23 }
24 return profits[n - 1];
25}Similar to the Python approach, the C++ implementation uses a vector to maintain the profit states. We iterate through transactions and update the maximum differences dynamically to calculate possible profits over 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.