123. Best Time to Buy and Sell Stock III

  int maxProfit(vector<int>& prices) {
        
         int n = prices.size();
        if(n==0)
            return 0;
        vector<int> left(n),right(n);
        
        //Fill 1st transaction (LEFT)
        int leftMin = prices[0];
        for(int i=1;i<n;++i)
        {
            left[i] = max(left[i-1],prices[i]-leftMin);
            leftMin = min(leftMin,prices[i]);
        }
        
        //Fill 2nd transaction (RIGHT)
        int rightMax = prices[n-1];
        for(int i=n-2;i>=0;--i)
        {
            right[i] = max(right[i+1],rightMax-prices[i]);
            rightMax = max(rightMax,prices[i]);
        }
        
        //Find the max-profit value
        int profit = right[0];
        for(int i=1;i<n;++i)
            profit = max(profit,left[i-1]+right[i]);
        
        return profit;
        
    }
//Memoization
class Solution {
   /*   
        pos->current position
        t->transactions done
        bought->If current stock is bought
    */
    vector<vector<vector<int>>> mem;
    int recursion(vector<int>& prices,int pos,int t,bool bought)
    {
        if(pos>=prices.size() || t==0)      //Out of bounds case
            return 0;
        if(mem[bought][t][pos]!=-1)     //Return if already calculated
            return mem[bought][t][pos];
        
        //3 choices for a position-->Buy/Sell/Skip
        int result = recursion(prices,pos+1,t,bought);    //SKIP
        if(bought)
            result = max(result,recursion(prices,pos+1,t-1,false)+prices[pos]);   //SELL
        else
            result = max(result,recursion(prices,pos+1,t,true)-prices[pos]);    //BUY
        
        mem[bought][t][pos] = result;
        return result;
    }
public:
    int maxProfit(vector<int>& prices) {
        mem.resize(2,vector<vector<int>>(3,vector<int>(prices.size(),-1)));
        int res = recursion(prices,0,2,false);
        return res;
    }
};