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.
1#include <vector>
2#include <algorithm>
3#include <iostream>
4
5int maxProfit(std::vector<int>& prices) {
6 if (prices.empty()) return 0;
7 int firstBuy = INT_MIN, firstSell = 0, secondBuy = INT_MIN, secondSell = 0;
8
9 for (int price : prices) {
10 firstBuy = std::max(firstBuy, -price);
11 firstSell = std::max(firstSell, firstBuy + price);
12 secondBuy = std::max(secondBuy, firstSell - price);
13 secondSell = std::max(secondSell, secondBuy + price);
14 }
15 return secondSell;
16}
17
18int main() {
19 std::vector<int> prices = {3, 3, 5, 0, 0, 3, 1, 4};
20 std::cout << "Max Profit: " << maxProfit(prices) << std::endl;
21 return 0;
22}This C++ solution uses vector for price storage and iterates over it, updating four state variables which represent different stages of profitability calculation for maximum profit with at most two transactions.
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.
public class StockProfit {
public static int MaxProfit(int[] prices) {
int n = prices.Length;
if (n <= 1) return 0;
int[] leftProfit = new int[n];
int[] rightProfit = new int[n + 1];
int minPrice = prices[0];
for (int i = 1; i < n; i++) {
leftProfit[i] = Math.Max(leftProfit[i - 1], prices[i] - minPrice);
minPrice = Math.Min(minPrice, prices[i]);
}
int maxPrice = prices[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightProfit[i] = Math.Max(rightProfit[i + 1], maxPrice - prices[i]);
maxPrice = Math.Max(maxPrice, prices[i]);
}
int maxProfit = 0;
for (int i = 0; i < n; i++) {
maxProfit = Math.Max(maxProfit, leftProfit[i] + rightProfit[i]);
}
return maxProfit;
}
public static void Main() {
int[] prices = new int[] { 3, 3, 5, 0, 0, 3, 1, 4 };
Console.WriteLine("Max Profit: " + MaxProfit(prices));
}
}C# approach deploys two arrays to manage profitability from each side, facilitating combination and determination of maximal income based on entire transactional spectrum. Utilization respects an even balance of temporal and spatial resource expenditure.