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

须要注意的是，能够操作两次买卖。可是第二次买入必须在第一次卖出之后才干操作。所以思路就是先正序使用贪心计算每一天之前买入卖出可能达到的最大收益，拿数组记录下来。再逆序计算每一天相应的之后买入卖出可能达到的最大收益，拿数组记录下来。然后将两个数组中每一天相应的两种情况能够实现的收益之和，得到最大值即为能够实现的最大收益。code例如以下：

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if(prices.empty())
            return 0;
        int n = prices.size();
        vector<int> pre(n,0);
        vector<int> post(n,0);
        int curMin = prices[0];
        int curMax = prices[n-1];
        int result=0;
        for(int i=1; i<n; i++)
        {
            curMin = curMin<prices[i] ? curMin : prices[i];
            int diff = prices[i]-curMin;
            pre[i] = pre[i-1]>diff ? pre[i-1] : diff;
        }
        for(int i=n-2; i>=0; i--)
        {
            curMax = curMax>prices[i] ? curMax : prices[i];
            int diff = curMax-prices[i];
            post[i] = post[i+1]>diff ?
 post[i+1] : diff;
        }
        for(int i=1; i<n; i++)
        {
            result = result>(pre[i]+post[i]) ?
 result : (pre[i]+post[i]);
        }
        return result;
    }
};