123. Best Time to Buy and Sell Stock III

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).

分析：

1.对于任何一个 i， 将数列分成两部分 [0, i] [i , n-1];
2. left[i] 记录在i的左边最大profit , right[i] 记录在i的右边最大profit
3. 再扫一遍得到最大 left[i] + right[i]

O(3N)

//将数列分成两部分 [0, i] [i , n-1];
// left[i] , right[i]
//再扫一遍得到最大 left[i] + right[i]
public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length <= 1)
            return 0;
        int N = prices.length;
        int left[] = new int[N];
        left[0] = 0;
        int min = prices[0];
        int right[] = new int[N];
        right[N-1] = 0;
        int max = prices[N-1];
        for(int i = 1 ; i < N; i++){
           min = Math.min(min, prices[i]);
           left[i] = Math.max(left[i-1], prices[i] - min);
        }
        for(int i = N-2 ; i >= 0 ; i--){
            max = Math.max(max, prices[i]);
            right[i] = Math.max(right[i+1], max - prices[i]);
        }
        int maxProfit = 0;
        for(int i = 0; i < N ; i++){
            maxProfit = Math.max(maxProfit , left[i] + right[i]);
        }
        return maxProfit;
    }
}