康瑞部落

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

解题思路：

题意为给定每天的股价，求最多两次交易最多的利润是多少？

我的想法是，最多一次交易的利润为P1（前面已经算出来了），最多两次的交易为P2，然后返回max(P1, P2)。

对于两次交易，可以看成两次一次交易。每次交易我们是在波峰/波谷中，因此，我们只需在每次的波峰/波谷中进行划分即可。

代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<int> uniquePrices = uniqueNeighbor(prices);
        int len = uniquePrices.size();
        if(len == 0 || len == 1){
            return 0;
        }
        int oneProfit = maxProfitHelper(uniquePrices, 0, len-1); //一次交易
        //分成两次交易，每个波谷（或者波峰剪切）
        int twoProfit = 0;
        for(int i=1; i<len-1; i++){
            if(uniquePrices[i]<uniquePrices[i-1] && uniquePrices[i]<uniquePrices[i+1]){
                twoProfit = max(twoProfit, maxProfitHelper(uniquePrices, 0, i) +  maxProfitHelper(uniquePrices, i, len - 1));
            }
        }
        return max(oneProfit, twoProfit);
    }
    
    //表示从start到end之间最多交易一次的最大利润
    int maxProfitHelper(vector<int>& prices, int start, int end){
        if(start>=end){
            return 0;
        }
        int result = 0;
        int minPrices = prices[start];
        for(int i=start+1; i<=end; i++){
            minPrices = min(prices[i], minPrices);
            result = max(result, prices[i] - minPrices);
        }
        return result;
    }
    vector<int> uniqueNeighbor(vector<int>& prices){
        vector<int> result;
        int len = prices.size();
        if(len == 0){
            return result;
        }
        result.push_back(prices[0]);
        for(int i=1; i<len; i++){
            if(result[result.size()-1]!=prices[i]){
                result.push_back(prices[i]);
            }
        }
        return result;
    }
};

注意这里首先将相邻价格的天合成一天（对结果没有影响），然后再计算，能够大大减少计算次数。但是最差的时间复杂度为O(n^2)，空间复杂度为O(1)。

另外一种方法是动态规划法。代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if(len<=1){
            return 0;
        }
        vector<int> left(len, 0);
        vector<int> right(len, 0);
        
        left[0] = 0;
        int minPrices = prices[0];
        for(int i=1; i<len; i++){
            minPrices = min(prices[i], minPrices);
            left[i] = max(left[i-1], prices[i]-minPrices);
        }
        
        right[len - 1] = 0;
        int maxPrices = prices[len - 1];
        for(int i=len-2; i>=0; i--){
            maxPrices = max(prices[i], maxPrices);
            right[i] = max(right[i+1], maxPrices - prices[i]);
        }
        
        int maxProfit = 0;
        
        for(int i=0; i<len; i++){
            maxProfit = max(maxProfit, left[i] + right[i]);
        }
        
        return maxProfit;
    }
};