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

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

代碼如下：

int maxProfit(vector<int> &prices) {
        int n=prices.size();
        if(n<=1)return 0;
        vector<int> left(n,0);
        vector<int> right(n,0);
        int minl=prices[0];
        for(int i=1;i<n;i++)
        {
            minl=std::min(minl,prices[i]);
            left[i]=std::max(left[i-1],prices[i]-minl);
        }
        int maxr=prices[n-1];
        for(int i=n-2;i>=0;i--)
        {
            maxr=std::max(maxr,prices[i]);
            right[i]=std::max(right[i+1],maxr-prices[i]);
        }
        int sum=0;
        for (int i=0;i<n;i++)
            sum=std::max(sum,left[i]+right[i]);
        return sum;
    }