Best Time to Buy and Sell Stock III

 [Thoughts]
One dimensional dynamic planning.
Given an i, split the whole array into two parts:
[0,i] and [i+1, n], it generates two max value based on i, Max(0,i) and Max(i+1,n)
So, we can define the transformation function as:
Maxprofix = max(Max(0,i) + Max(i+1, n))  0<=i<n
------------------------------------------------------------
先从前往后找出每个i（i>0)之前（包括此位置）交易所有可能最大profit值，记录为 max_left[i].
在从后往前找出每个位置之后交易所有可能最大profit值，记录为 max_right[i].
接下来就简单了。一个for loop 解决问题。

 Solution: dp. max profit = max { l2r[0...i] + r2l[i+1...N-1] }.
0 <= i <= N-1


    int maxProfit(vector<int> &prices) {
        int N = prices.size();
        if (N <= 1) return 0;
        
        int l2r[N], r2l[N];
        l2r[0] = 0;
        r2l[N-1] = 0;
        
        int minn = prices[0];
        for (int i = 1; i < N; ++i)
        {
            minn = min(minn, prices[i]);
            l2r[i] = max(l2r[i-1], prices[i] - minn);
        }
        
        int maxx = prices[N-1];
        for (int i = N-2; i >= 0; --i)
        {
            maxx = max(maxx, prices[i]);
            r2l[i] = max(r2l[i+1], maxx - prices[i]);
        }
        
        int res = l2r[N-1];
        for (int i = 0; i < N-1; ++i)
            res = max(res, l2r[i] + r2l[i+1]);
        return res;
    }

类比： 此题可以candy的次优解法对看：http://codeganker.blogspot.com/2014/03/candy-leetcode.html