学步园

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

解题思路来自：http://blog.csdn.net/fightforyourdream/article/details/14503469

题中要求为两次交易，所以一定会对目标数据进行二分。一开始使用了迭代算法，计算每个二分的max profit，结果计算超时，因为存在多次重复计算，算法改写后，使用数组存储中间数据，并可以通过数组来直接计算新加入prices元素的对应的两个数组值，这个是非常巧妙的地方。

最终，时间复杂度O(2n)，空间复杂度O(2n)

class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        int N = prices.length;
        if(N<2)
            return 0;
        int[] left=new int[N];
        int[] right=new int[N];
        int min = prices[0];
        int max = prices[N-1];
        for(int i=1;i<N;i++){
            left[i] = Math.max(left[i-1],prices[i]-min);  // 当前可能的最大值
            min = Math.min(min,prices[i]);
            
            right[N-1-i] = Math.max(right[N-i],max - prices[N-1-i]);
            max = Math.max(max,prices[N-1-i]);
        }
        
        int res=0;
        for(int i=0;i<N;i++)
            res = Math.max(left[i]+right[i],res);
        return res;
    }
};