LeetCode 123. Best Time to Buy and Sell Stock III [Hard] [C++] 解題筆記

Say you have an array for which the i^th 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 (i.e., you must sell the stock before you buy again).

 

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Example 4:

Input: prices = [1]
Output: 0

想法:

    這題是 122. Best Time to Buy and Sell Stock II 和 121. Best Time to Buy and Sell Stock

的進階題，差別在於說這題限制最多只能進行兩次交易(買進兩次賣出兩次)，因此必須要找出獲利最大的兩次交易。

題目要求在買新股票之前必須先賣掉手上持有的股票，因此同一時間手上只能持有一隻股票，所以我們可以分析如下:

假設: 

    hold1[k] 表示第 k 天手上持有的第一支股票目前的損益

    sold1[k] 表示第 k 天清空手上第一支股票之後目前的損益

    hold2[k] 表示第 k 天手上持有的第二支股票目前的損益

    sold2[k] 表示第 k 天清空手上第二支股票之後目前的損益

則可以得知(prices[k] 為第 k 天的股價

    // 第 k 天持有可能為第 k 天買進 或是 之前就持有了 (都還沒買任何一隻股票前損益為 0)

    hold1[k] = max(0 - prices[k], hold1[k - 1])  

    // 第 k 天賣掉第一支股票的損益可能為第 k 天當天賣掉 或是 之前就賣掉了

    sold1[k] = max(hold1[k - 1] + prices[k], sold1[k - 1])

    // 第 k 天持有第二支股票可能為第 k 天買進第二支股票(表示前一天之前要先把第一支股票賣掉)

    // 或是 之前就持有第二支股票了

    hold2[k] = max(sold1[k - 1] - prices[k], hold2[k - 1])

    // 第 k 天賣掉第二支股票的損益可能為第 k 天當天賣掉第二支股票 或是 之前就賣掉了

    sold2[k] = max(hold2[k - 1] + prices[k], sold2[k - 1])

最後再取最後一天的 max(sold1, sold2)，因為目標是最大獲利因此最後一天的 hold1, hold2不用列入考慮

(最後一天還沒賣掉絕對不會是最大獲利，根本沒有獲利)

Complexity: O(n) time.

完整程式碼:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int hold1 = INT_MIN; 
        int sold1 = 0;
        int hold2 = INT_MIN;
        int sold2 = 0;
        for (int i = 0; i < prices.size(); i++) {
            int hold1_pre = hold1;
            int sold1_pre = sold1;
            int hold2_pre = hold2;
            int sold2_pre = sold2;
            
            // 當天買進 or 前一天就持有
            hold1 = max(0 - prices[i], hold1_pre);
            // 當天賣掉之前買進的 or 不買不賣 維持之前賣出的結果
            sold1 = max(hold1_pre + prices[i], sold1_pre);
            // 當天買進，表示之前賣掉第一支股票 or 繼續持有手上的第二隻股票
            hold2 = max(sold1_pre - prices[i], hold2_pre);
            // 當天賣掉之前持有的第二隻股票 or 維持之前賣出的結果
            sold2 = max(hold2_pre + prices[i], sold2_pre);
        }
        
        return max(sold1, sold2);
    }
};