[LeetCode] Best Time to Buy and Sell Stock III

Problem:

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution:O(n)

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

Key Concept:divide two part to solve the problem