給定每日股價
prices與整數k，最多完成 k 筆交易，求最大利潤（同一時間最多持有一股，先賣才能再買）。
Example:
Input: k = 2, prices = [2,4,1] Output: 2（第 1 天買 2、第 2 天賣 4）
Input: k = 2, prices = [3,2,6,5,0,3] Output: 7（買 2 賣 6 賺 4；買 0 賣 3 賺 3）
Intuition
TIP
核心思路：123 的一般化——用 buy[j]、sell[j] 兩個長度 k+1 的陣列。另外當 k 大到 ≥ n/2，等於不限次數，退化成貪心收所有上漲段。
buy[j]：完成第 j 次買後的最大現金；sell[j]：完成第 j 次賣後的最大利潤- 轉移：
buy[j] = max(buy[j], sell[j-1] - p)、sell[j] = max(sell[j], buy[j] + p) - 大 k 捷徑：一筆交易至少佔兩天，
k ≥ n/2時限制失效 → 直接加總每段正向價差（等同 122） - 沒有捷徑會讓最差情況
O(n·k)在 k 很大時退化，捷徑避免之
Approaches
⭐ k-Transaction DP + Large-k Greedy Shortcut — O(n·k) / O(k)
- Idea: 內層對 j = 1..k 更新 buy/sell；k 過大時改用無限次交易的貪心
- Time:
O(n·k)（大 k 時O(n)） - Space:
O(k)- 兩個長度 k+1 陣列
class Solution {
fun maxProfit(k: Int, prices: IntArray): Int {
val n = prices.size
if (n == 0 || k == 0) return 0
// k 夠大 → 等於不限次數，收所有上漲段
if (k >= n / 2) {
var profit = 0
for (i in 1 until n) {
if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1]
}
return profit
}
val buy = IntArray(k + 1) { Int.MIN_VALUE } // 第 j 次買後最大現金
val sell = IntArray(k + 1) // 第 j 次賣後最大利潤
for (p in prices) {
for (j in 1..k) {
buy[j] = maxOf(buy[j], sell[j - 1] - p)
sell[j] = maxOf(sell[j], buy[j] + p)
}
}
return sell[k]
}
}Note: Why inner loop ascends from j = 1
buy[j] 依賴同一輪剛更新的 sell[j-1]（同一天可從第 j-1 次賣的狀態接著做第 j 次買），所以 j 由小到大更新是對的；而 sell[j] 依賴同一輪的 buy[j]，順序一致不會用到尚未更新的未來狀態。
🔑 Takeaways
- Pattern: 狀態機 DP 的一般化（交易次數作為第二維），123 是 k = 2 的特例
- Key trick:
k ≥ n/2的貪心捷徑同時處理「k 很大」與避免無謂計算；buy/sell 陣列由 j 升序就地更新即可壓到O(k)空間