Best_time_to_buy_and_sell_stock_III

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

class Solution {  
public:  
    int maxProfit(vector<int> &prices) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        int profit = 0, n = prices.size();  
        if (n == 0) {  
            return 0;  
        }  
        int l[n], r[n];  
        memset(l, 0, sizeof(int) * n);  
        memset(r, 0, sizeof(int) * n);  
        int min = prices[0];  
        for (int i = 1; i < n; i++) {  
            l[i] = prices[i] - min > l[i - 1] ? prices[i] - min : l[i - 1];          
            min = prices[i] < min ? prices[i] : min;  
        }  
        int max = prices[n - 1];  
        for (int i = n - 2; i >= 0; i--) {  
            r[i] = max - prices[i] > r[i + 1] ? max - prices[i] : r[i + 1];  
            max = prices[i] > max ? prices[i] : max;  
        }  
        for (int i = 0; i < n; i++) {  
            profit = l[i] + r[i] > profit ? l[i] + r[i] : profit;  
        }  
        return profit;        
    }  
};  


REMARK:
1 SUPER HARD.Hard for both thinking and coding.
IDEA: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

对于点j+1，求price[0..j+1]的最大profit时，很多工作是重复的，在求price[0..j]的最大profit中已经做过了。
类似于Best Time to Buy and Sell Stock，可以在O(1)的时间从price[0..j]推出price[0..j+1]的最大profit。
但是如何从price[j..n-1]推出price[j+1..n-1]？反过来思考，我们可以用O(1)的时间由price[j+1..n-1]推出price[j..n-1]。
最终算法：
数组l[i]记录了price[0..i]的最大profit，
数组r[i]记录了price[i..n]的最大profit。
已知l[i]，求l[i+1]是简单的，同样已知r[i]，求r[i-1]也很容易。
最后，我们再用O(n)的时间找出最大的l[i]+r[i]，即为题目所求。