Leetcode Best Time to Buy and Sell Stock III problem solution

In this Leetcode Best Time to Buy and Sell Stock III problem solution, we have given an array of prices where prices[i] is the price of a given stock on an ith day. Find the maximum profit you can achieve. You may complete at most two transactions.

Problem solution in Python.

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

Problem solution in Java.

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;
}

Problem solution in C++.

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]);
    }
};

Problem solution in C.

#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;
}

coding problems