123. Best Time to Buy and Sell Stock III

1.問題

• 你擁有一個代表每天股票價格的list, 最多有兩次交易, 計算出最高的獲利價格

2.想法

• 提問

  • 確認題意:

• function header, parameter

• test input

• 觀察

• 說明想法

  • 對某天來說的最大獲利是在該天賣掉, 當天再次買進

  • 區域最高獲利 (每天的最高獲利)

    • 第一次買剛好是第一次賣前的最低價格

    • 第二次賣正好是第一次賣後的最高價格

  • 找出區域最大獲利中的最大值

• 測試計算複雜度

3.程式碼

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        if (size < 2) {
            return 0;
        }
        
        //對某一天來說, 第一次交易 (該天價格 - 最小價格)
        vector<int> first(prices.size(), 0);
        int minV = prices[0];
        for (int i = 1; i < size; i++) {
            first[i] = max(first[i - 1], (prices[i] - minV));
            minV = min(minV, prices[i]);
        }
        
        //對某一天來說, 第二次交易 (最大價格 - 該天價格)
        int maxV = prices[size - 1];
        int res = 0;
        for (int i = size - 2; i >= 0; i--) {
            maxV = max(maxV, prices[i]);
            res = max(res, (maxV - prices[i] + first[i]));
        }
        
        return res;
    }
};