Sponsored
Sponsored
This approach utilizes dynamic programming with four state variables to track the profit in various stages of transactions: before the first buy, after the first buy (before the sell), after the first sell (before the second buy), and after the second buy (before the final sell). By iterating over the prices array, we update these states with the maximum profit achievable at each step.
Time Complexity: O(n), where n is the number of days (prices length).
Space Complexity: O(1), constant space used regardless of input size.
This solution initializes four state variables representing the different transaction stages. We iterate over the price list to update these states, maximizing profit at each step. The final state, secondSell, holds the maximum profit obtainable.
This approach involves creating two arrays that store the maximum profit achievable from the left side to each index and from each index to the right in the prices array. Combining these two arrays helps derive the total maximum profit achievable through two transactions.
Time Complexity: O(n), as we iterate twice through prices.
Space Complexity: O(n), due to the use of two auxiliary arrays.
1#include <stdio.h>
2#include <stdlib.h>
3
4int maxProfit(int* prices, int pricesSize) {
5 if (pricesSize <= 1) return 0;
6 int* leftProfit = (int*)calloc(pricesSize, sizeof(int));
7 int* rightProfit = (int*)calloc(pricesSize + 1, sizeof(int)); // rightProfit has one extra space for convenience
8
9 int minPrice = prices[0];
10 for (int i = 1; i < pricesSize; i++) {
11 leftProfit[i] = prices[i] < minPrice ? leftProfit[i - 1] : max(leftProfit[i - 1], prices[i] - minPrice);
12 minPrice = prices[i] < minPrice ? prices[i] : minPrice;
13 }
14
15 int maxPrice = prices[pricesSize - 1];
16 for (int i = pricesSize - 2; i >= 0; i--) {
17 rightProfit[i] = prices[i] > maxPrice ? rightProfit[i + 1] : max(rightProfit[i + 1], maxPrice - prices[i]);
18 maxPrice = prices[i] > maxPrice ? prices[i] : maxPrice;
19 }
20
21 int maxProfit = 0;
22 for (int i = 0; i < pricesSize; i++) {
23 maxProfit = leftProfit[i] + rightProfit[i] > maxProfit ? leftProfit[i] + rightProfit[i] : maxProfit;
24 }
25
26 free(leftProfit);
27 free(rightProfit);
28 return maxProfit;
29}
30
31int max(int a, int b) {
32 return a > b ? a : b;
33}
34
35int main() {
36 int prices[] = {3, 3, 5, 0, 0, 3, 1, 4};
37 int size = sizeof(prices) / sizeof(prices[0]);
38 printf("Max Profit: %d\n", maxProfit(prices, size));
39 return 0;
40}This C solution uses two auxiliary arrays to track maximal profit potential from either direction along the price sequence. Profit amounts are compiled crosswise to determine peak profitability over the entire period.
Solve with full IDE support and test cases