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

題目描述

給定股票每日價格數組 prices，最多完成 k 筆交易（買入後必須賣出才能再買），求最大利潤。k 可大於 n/2。

動態規劃：局部最優與全局最優

定義兩個二維狀態（可優化為一維）：

• local[i][j]：前 i 天、最多 j 筆交易、且第 i 天必須賣出的最大利潤（局部最優，最後一次交易固定在今天）。
• global[i][j]：前 i 天、最多 j 筆交易的最大利潤（全局最優，最後一天不一定交易）。

遞推公式

diff = prices[i] - prices[i-1]
local[i][j] = max(global[i-1][j-1] + max(diff, 0), local[i-1][j] + diff)
global[i][j] = max(global[i-1][j], local[i][j])

• global[i-1][j-1] + max(diff,0)：第 i-1 天結束前完成 j-1 筆，第 i 天作為第 j 筆交易的賣出日（若 diff>0 獲利，否則不交易等價於不買）。
• local[i-1][j] + diff：延續第 j 筆交易，原本在第 i-1 天賣出，現推遲到第 i 天賣出，利潤增加 diff。

空間優化：一維滾動數組

注意 j 必須從 k 遞減到 1，因為 local[j] 依賴舊的 global[j-1] 和 local[j]。

完整代碼 (C++)

class Solution {
public:
    int maxProfit(int k, vector& prices) {
        int n = prices.size();
        if (n <= 1 || k == 0) return 0;
        // k >= n/2 退化為無限次交易 (LeetCode 122)
        if (k >= n/2) return unlimitedProfit(prices);

        vector global(k+1, 0), local(k+1, 0);
        for (int i = 1; i < n; ++i) {
            int diff = prices[i] - prices[i-1];
            for (int j = k; j >= 1; --j) {
                local[j] = max(local[j] + diff, global[j-1] + max(diff, 0));
                global[j] = max(global[j], local[j]);
            }
        }
        return global[k];
    }

private:
    int unlimitedProfit(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;
    }
};

複雜度

• 時間：O(n·k)
• 空間：O(k)

關鍵點總結

1. 狀態拆分為「必在今天賣出」與「不必今天賣出」，巧妙處理交易邊界。
2. k >= n/2 時退化為貪心（LeetCode 122），避免 O(n²) 超時。
3. 一維數組逆序更新是經典 DP 優化技巧。