LeetCode Best Time to Buy and Sell the Stock III&VI

DP. Finding the best situation from 0 - i (Left) and i+1, prices.length-1 (Right).


public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;
     
        int maxProfit = 0;
        int len = prices.length;
        int[] left = new int[len];
        int[] right = new int[len];
     
        process(prices, left, right);
     
        for (int i=0; i<len; i++) {
            maxProfit = Math.max(maxProfit, left[i] + right[i]);
        }
        return maxProfit;
    }
 
    private void process(int[] prices, int[] left, int[] right) {
        //Left side
        left[0] = 0;
        int min = prices[0];
        for (int i=1; i<left.length; i++) {
            left[i] = Math.max(left[i-1], prices[i] - min);
            min = Math.min(min, prices[i]);
        }
     
        //right side
        right[prices.length-1] = 0;
        int max = prices[prices.length-1];
        for (int i=prices.length-2; i>=0; i--) {
            right[i] = Math.max(right[i+1], max - prices[i]);
            max = Math.max(max, prices[i]);
        }
    }

Find a better solution.
Reference
http://blog.csdn.net/linhuanmars/article/details/23236995
public int maxProfit(int[] prices) {
        if (prices==null || prices.length==0) return 0;
        int numTrans = 2;
        int[] local = new int[numTrans+1];
        int[] global = new int[numTrans+1];
        for (int i=0; i<prices.length-1; i++) {
            int diff = prices[i+1]-prices[i];
            for (int j=numTrans; j>0; j--) {
                local[j]=Math.max(global[j-1]+Math.max(diff,0), local[j]+diff);
                global[j]=Math.max(global[j],local[j]);
            }
        }
        return global[numTrans];
    }