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

题意：获取股票最大收益，最多可交易两次，且必须完成一桩交易之后才能进行另一桩交易。当然，可以第i天卖出后又当天买回。

因为最多两次交易，很容易联想到将数组分为两部分，对两部分数组分别求最大值，然后将两个最大值相加，经多次比较，得到总的最大值。但是这会出现一个问题，时间复杂度太大，为。经测试，这种方式会导致Time Limited Exceed的错误。

那么现在需要考虑一下有没有可以改进的方法，答案是有的，可以利用一维的动态规划来做，因为我们可以观察到，之前的方案之所以复杂度太大是因为有很多重复的计算。而动态规划可以采取的方式是：

1）新开一个数组maxProfitWith，这个数组用来保存第i天可以获得的最大收益。算法复杂度为。

2）将prices数组都遍历一遍之后，可以知道最后一项，即maxProfitWith[size-1]即为遍历一遍时的最大收益。

3）我们再逆序遍历一遍，计算当前i到最后一天的最大收益，与之前的0至第i天的最大收益相加，可以得到总的最大收益finalProfit，比较之后，可以得到最终结果，算法复杂度也是。

4）最终的算法复杂度就是。

class Solution {public:    int maxProfit(vector &prices) {        if(prices.empty())            return 0;        int size=prices.size();        int lowest=prices[0];        vector maxProfitWith;        maxProfitWith.push_back(0);        int maxProfit=0;        for(int i=1;imaxProfit)                maxProfit=profit;            maxProfitWith.push_back(maxProfit);            if(prices[i]=0;i--)        {            int profit=highest-prices[i];            if(profit>maxProfit)                maxProfit=profit;            int maxSum=maxProfitWith[i]+maxProfit;            if(maxSum>finalProfit)                finalProfit=maxSum;            if(prices[i]>highest)                highest=prices[i];        }        return finalProfit;    }};