Leetcode Best Time to Buy and Sell Stock III problem solution

l = len(prices)
        if l < 2:
            return 0
        profit = 0
        dp1,dp2 = [0]*l,[0]*(l+1)
        minval,maxval = prices[0],prices[-1]
        for i in xrange (1,l):
            if prices[i] < minval:
                minval = prices[i]
                dp1[i] = dp1[i-1]
            else:
                dp1[i] = max(dp1[i-1],prices[i]-minval)
        for i in xrange (l-1,-1,-1):
            if prices[i] > maxval:
                maxval = prices[i]
                dp2[i] = dp2[i+1]
            else:
                dp2[i] = max(dp2[i+1],maxval - prices[i])
        for i in xrange (l):
            profit = max(profit,dp1[i] + dp2[i+1])
        return profit

public int maxProfit(int[] prices) {
    int res = 0;
    int len = prices.length;
    if(len < 2) return 0;
    int[] leftmax = new int[len];
    int[] rightmax = new int[len];
    leftmax[0] = 0;
    rightmax[len-1] = 0;
    int left = prices[0];
    int right = prices[len-1];
    for(int i = 1; i < len; i++) {
        left = Math.min(left, prices[i]);
        leftmax[i] = Math.max(leftmax[i-1], prices[i] - left);
        right = Math.max(right, prices[len-1-i]);
        rightmax[len-1-i] = Math.max(rightmax[len-i], right - prices[len-1-i]);
    }
    for(int i = 0; i < len; i++) {
        res = Math.max(res, leftmax[i] + rightmax[i]);
    }
    return res;
}

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int states[2][4] = {INT_MIN, 0, INT_MIN, 0};
        int len = prices.size(), i, cur = 0, next =1;
        for(i=0; i<len; ++i)
        {
            states[next][0] = max(states[cur][0], -prices[i]);
            states[next][1] = max(states[cur][1], states[cur][0]+prices[i]);
            states[next][2] = max(states[cur][2], states[cur][1]-prices[i]);
            states[next][3] = max(states[cur][3], states[cur][2]+prices[i]);
            swap(next, cur);
        }
        return max(states[cur][1], states[cur][3]);
    }
};

#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b

int* getLeftMaxProfit(int *prices, int pricesSize){
    int *leftP=malloc(pricesSize*sizeof(int));
    
    int maxProfit=0;
    int minPrice=prices[0];
    leftP[0]=0;
    for(int i=1;i<pricesSize;i++){
        maxProfit=max(maxProfit,prices[i]-minPrice);
        minPrice=min(minPrice,prices[i]);
        leftP[i]=maxProfit;
    }    
    return leftP;
}

int* getRightMaxProfit(int *prices, int pricesSize){
    int *rightP=malloc(pricesSize*sizeof(int));
    
    int maxProfit=0;
    int maxPrice=prices[pricesSize-1];
    rightP[pricesSize-1]=0;
    for(int i=pricesSize-2;i>=0; i--){
        maxProfit=max(maxProfit, maxPrice-prices[i]); 
        maxPrice=max(maxPrice, prices[i]); 
        rightP[i]=maxProfit;
    }    
    return rightP;
}

int maxProfit(int* prices, int pricesSize){
    int *leftP;
    int *rightP;
    
    leftP=getLeftMaxProfit(prices, pricesSize);
    rightP=getRightMaxProfit(prices, pricesSize);
    
    int maxProfit=0;
    for(int i=0;i<pricesSize-1;i++){
        maxProfit=max(maxProfit,leftP[i]+rightP[i+1]); 
    }
    maxProfit=max(maxProfit,leftP[pricesSize-1]);
    maxProfit=max(maxProfit,rightP[0]);
    
    return maxProfit;
}