題目描述:給定股票價格陣列和最多交易次數 k,求最大利潤。同一時刻只能持有一股。
解題思路:若 k >= n/2(可做所有交易),直接用貪心(累加所有正差)。否則維護大小為 k 的 buy[j] 和 sell[j] 陣列(j = 第幾次交易),每天從第 k 次到第 1 次更新(避免同日重複使用)。這是 LC 123 四變數解法的推廣。
時間複雜度:O(n × k) — n 天,每天更新 k 個狀態。
空間複雜度:O(k) — buy 和 sell 各需 k 個元素。
1. If k >= n/2: return sum of all positive daily differences (greedy)
2. Initialize buy[k] = INT_MIN, sell[k] = 0
3. For each price:
For j from k-1 down to 0:
sell[j] = max(sell[j], buy[j] + price)
buy[j] = max(buy[j], (j > 0 ? sell[j-1] : 0) - price)
4. Return sell[k-1]完整 DP dp[i][j][0/1] O(n×k) 空間:直觀的三維 DP — 容易理解,但實作繁瑣且 O(nk) 空間不如滾動陣列優化。
優先隊列貪心 O(n log n):將交易拆分為買賣對,用優先隊列維護最大利潤,可在 O(n log k) 時間解決 — 進階技巧,理解難度高。