LeetCode 121/122/123 Best Time to Buy and Sell Stock I/II/III 完整系列解析

系列問題統覽

I 題：最多一筆交易

維護歷史最低買入價，計算當天賣出利潤，取最大值。

int maxProfit(vector& prices) {
    int minPrice = INT_MAX, maxProfit = 0;
    for (int p : prices) {
        minPrice = min(minPrice, p);
        maxProfit = max(maxProfit, p - minPrice);
    }
    return maxProfit;
}

II 題：無限次交易

貪心：只要明天價格高於今天，今天買明天賣。等價於累加所有上升段差值。

int maxProfit(vector& prices) {
    int profit = 0;
    for (int i = 1; i < prices.size(); ++i)
        if (prices[i] > prices[i-1])
            profit += prices[i] - prices[i-1];
    return profit;
}

III 題：最多兩筆交易

分治動態規劃：

• `left[i]` = [0..i] 區間內最多一筆交易的最大利潤
• `right[i]` = [i..n-1] 區間內最多一筆交易的最大利潤
• 答案 = max_{i} (left[i] + right[i])

int maxProfit(vector& prices) {
    int n = prices.size();
    if (n <= 1) return 0;
    
    vector left(n), right(n);
    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);
    }
    
    int maxPrice = prices[n-1];
    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;
}

通用化：最多 k 筆交易 (LeetCode 188)

DP 狀態：`dp[k][i]` = 前 i 天最多 k 筆交易最大利潤。優化至 O(kn) 時間、O(n) 空間。當 k ≥ n/2 時退化為 II 題貪心。

核心洞察總結

1. I 題：單極值追蹤
2. II 題：局部最優疊加 = 全局最優
3. III 題：空間分治（前綴/後綴）將雙交易解耦
4. 通用 k 題：動態規劃 + 狀態機優化