[GeeksforGeeks] Buy and Sell stocks twice for max profit

Buy and Sell stocks twice for max profit

Analysis:
The question can be solved by DP using two arrays left[] and right[].
left[i] represents max profit to be made between day [0..i]
right[i] represents max profit to be made between day [i, n-1].

The ultimate max profit would be max sum of left[i] + right[i]

Solution:
#include<iostream>
using namespace std;

// Returns maximum profit with two transactions on a given
// list of stock prices, price[0..n-1]
int maxProfit(int price[], int n)
{
    int left[n];
    int right[n];
    
    int i;
    for(i = 0; i < n;i++)
    {
    left[i] = 0;
    right[i] = 0;
    }
    
    int min_price = price[0], max_price = price[n-1];
    int max_profit = 0;
    
    for(i = 0; i < n; i++)
    {
    min_price = min_price < price[i] ? min_price : price[i];
    left[i] = price[i] - min_price > max_profit ? price[i] - min_price: max_profit;
    }
    
    max_profit = 0;
    right[n-1] = 0;
    
    for(i = n-2; i >=0; i--)
    {
    max_price = max_price > price[i] ? max_price : price[i];
    right[i] = max_price - price[i] > right[i+1] ? max_price - price[i] : right[i+1];
   
    }
    
    max_profit = 0;
    for(i = 0; i < n; i++)
    {
    max_profit = max_profit > left[i] + right[i] ? max_profit : left[i] + right[i];
    }
    
    return max_profit;
    
    
}

// Drive program
int main()
{
    int price[] = {2, 30, 15, 10, 8, 25, 80};
    int n = sizeof(price)/sizeof(price[0]);
    cout << "Maximum Profit = " << maxProfit(price, n);
    return 0;
}