[Leetcode] 123. 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).

思路：

1、O(n)空間複雜度的動态規劃：由于最多進行兩次交易，是以第一次交易和第二次交易的分割點就比較關鍵。我們定義left_max[i]表示在[0, i]區間内完成一筆交易所能獲得的最利潤，而right_max[i]則表示在[i, prices.size() - 1]區間内完成一筆交易所能獲得的最大利潤。顯然，left_max和right_max都可以通過線性掃描，采用貪心政策正确計算出來，最後線性掃描，取得最佳分割點即可。不過，最後别忘了将交易兩次的獲利和隻交易一次的最大獲利相比較，并取最大值（left_max[prices.size() - 1]或者right_max[0]）。

2、O(1)空間複雜度的動态規劃：可以交易兩次，是以可以記錄一下兩次買和兩次賣之後的最大利潤。因為可以交易兩次，是以第二次交易将會依賴于第一次的結果，即第二次買下一個股票剩下的利潤依賴于之前第一次賣掉股票之後的利潤——目前的股票價格。同理第二次賣掉一支股票之後剩下的利潤依賴于第二次買下一支股票之後剩下的利潤+目前的股票價格。注意，我們在這裡其實也就是把買入一隻股票當作了-prices[i]的收益。

代碼：

1、O(n)空間複雜度的動态規劃：

class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        if(prices.size() <= 1)
            return 0;
        vector<int> left_max(prices.size(), 0);
        vector<int> right_max(prices.size(), 0);
        int lowest_price = prices[0];
        for(int i = 1; i < prices.size(); ++i)
        {
            if(prices[i] < lowest_price)
                lowest_price = prices[i];
            left_max[i] = max(left_max[i - 1], prices[i] - lowest_price);
        }
        int highest_price = prices[prices.size() - 1];
        for(int i = prices.size() - 2; i >= 0; --i)
        {
            if(prices[i] > highest_price)
                highest_price = prices[i];
            right_max[i] = max(right_max[i + 1], highest_price - prices[i]);
        }
        int max_profit = 0;
        for(int i = 0; i < prices.size() - 1; ++i)
        {
            int sum_price = left_max[i] + right_max[i + 1];
            if(max_profit < sum_price)
                max_profit = sum_price;
        }
        return max(max_profit, right_max[0]);
    }
};
           

2、O(1)空間複雜度的動态規劃：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) {
            return 0;
        }
        int buy1 = INT_MIN, buy2 = INT_MIN, sell1 = 0, sell2 = 0;
        for (auto it = prices.begin(); it != prices.end(); ++it) {
            buy1 = max(buy1, -*it);
            sell1 = max(sell1, buy1 + *it);
            buy2 = max(buy2, sell1 - *it);
            sell2 = max(sell2, buy2 + *it);
        }
        return sell2;
    }
};