Best Time to Buy & Sell Stocks III

Link to problem at LeetCode

This is a famous 1-D DP problem. The problem seems to be a bit tricky in the first sight but the gist behind it is amazing. My solution is based on Divide and Conquer optimisation to O(n) Time Complexity and O(n) Space Complexity. I will be sharing my initial Greedy Approach which turned out to be wrong and then how I landed up to an optimal apporach.

The problem states you need to perform at most two transactions and determine the maxProfit obtained out of it. The transactions are in the way Buy -> Sell . No two transactions can overlap.

Intutiton :

1. Brute-Force : Greedy approach says find the all increasing sub-array in the prices and then in each sub-array determine maxPrice-minPrice and push it in a priority_queue/heap which then pops the greatest two profits and returns their sum.
   Example : prices = [2,3,4,2,1,2,3,2,4]
   In the above example if we try greedily we form the three increasing sub-arrays : [2 3 4] , [1,2,3] and [2,4].
   Thus we obtain profits : 2 , 2 and 2 out of them.
   We push them in the heap to obtain the max two profits and add them to get a total Profit of 4.
2. Better Approach : Divide and Conquer approach is a bit intuitive and require some observations in the above algorithm. The issue with the initial observation is there can be overlapping transactions which contributes to increased maxProfit for at most two transactions.
   For this one can visualise a line at every index which divides the prices into two arrays left and right parts.
   Left Array maintains the maxProfit in the left price array and so does the same Right Array.
   We return maxSum of Left and Right parts which gives us the final result.

Algorithm :

1. Find leftTransactions[] i.e. , for every index prices[i]-mini , where mini is minimum price and i is in [0..i] from left.
   Note : This is performed because we are performing Buy →Sell, which gives us profit when we have a min-valued stock bought first and then its selled at a higher price.
2. Find rightTransactions[] i.e. , for every index maxi-prices[i] , where maxi is the maximum price and i is in [i..prices.size()-1] from right.
   Note : This is performed because we are performing Buy →Sell, which gives us profit when we know max-valued stock selling first and then its at what lowest price it was bought at. Simply Mirror of above step.
3. Traverse leftTransactions[] to maintain prefix max profits.
4. Traverse rightTransactions[] to maintain suffix max profits.
5. For everyIndex in prices
   return maxProfit = max(maxProfit,leftTransactions[i-1]+rightTransactions[i])

#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define REP(i,a,b) for(int i=a;i<b;i++)
#define REPI(i,a,b) for(int i=a;i>=b;i--)
class Solution {
public:
void printArr(vi arr,string type){
        cout<<type<<" : ";
        for(auto ele:arr){
            cout<<ele<<" ";
        }
        cout<<endl;
}
int maxProfit(vector<int>& prices) {
        int size=prices.size();
        int n=size;
        vi leftTransaction(size,0);
        vi rightTransaction(size,0);
        int i;
        int mini=INT_MAX;
        REP(i,0,n){
            mini=min(prices[i],mini);
            leftTransaction[i]=prices[i]-mini;
        }
        int maxi=INT_MIN;
        REPI(i,n-1,0){
            maxi=max(maxi,prices[i]);
            rightTransaction[i]=maxi-prices[i];
        }
        maxi=INT_MIN;
        REP(i,0,n){
            maxi=max(maxi,leftTransaction[i]);
            leftTransaction[i]=maxi;
        }
        maxi=INT_MIN;
        REPI(i,n-1,0){
            maxi=max(maxi,rightTransaction[i]);
            rightTransaction[i]=maxi;
        }
        maxi=INT_MIN;
        
        REP(i,0,n){
            int left=0,right=0;
            if(i-1>0){
                left=leftTransaction[i-1];
            }
            right=rightTransaction[i];
            maxi=max(maxi,left+right);
        }
        
    return maxi;
  }
};