//将数列分成两部分 [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;
    }
}