LeetCode 筆記：Best Time to Buy and Sell Stock III - 最多兩筆交易最大利潤

題目描述

給定每日股價，最多完成兩筆交易，求最大利潤。交易不得重疊（必須賣出後再買）。

分割點 DP 思想

將時間線在某天 i 分為左右兩段：左段 [0..i] 完成第一筆交易，右段 [i..n-1] 完成第二筆。枚舉所有分割點，取最大值。

• left[i]：[0..i] 區間內單筆交易最大利潤（正向掃描，維護最小買入價）。
• right[i]：[i..n-1] 區間內單筆交易最大利潤（逆向掃描，維護最大賣出價）。
• 答案 = max(left[i] + right[i])。

代碼實現 (C++)

class Solution {
public:
    int maxProfit(vector& prices) {
        int n = prices.size();
        if (n <= 1) return 0;
        vector left(n), right(n);

        // 正向：left[i] = max(left[i-1], prices[i] - minPrice)
        int minPrice = prices[0];
        for (int i = 1; i < n; ++i) {
            minPrice = min(minPrice, prices[i]);
            left[i] = max(left[i-1], prices[i] - minPrice);
        }

        // 逆向：right[i] = max(right[i+1], maxPrice - prices[i])
        int maxPrice = prices[n-1];
        right[n-1] = 0;
        for (int i = n-2; i >= 0; --i) {
            maxPrice = max(maxPrice, prices[i]);
            right[i] = max(right[i+1], maxPrice - prices[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i)
            ans = max(ans, left[i] + right[i]);
        return ans;
    }
};

複雜度

• 時間：O(n) — 三次線性掃描。
• 空間：O(n) — 兩個輔助數組（可優化為 O(1) 但代碼較繁）。

關鍵點

1. 分割點枚舉將「兩筆不重疊交易」轉化為兩個獨立的「單筆交易」子問題。
2. 正向掃描求前綴最優，逆向掃描求後綴最優，是處理「不重疊區間最優和」的通用技巧。
3. 本題是 Stock IV (k=2) 的特例，理解本題有助於掌握通用 DP 狀態設計。