給定每日股價
prices，最多完成兩筆交易（買賣各算一次，且必須先賣再買，不能同時持有多股），求最大利潤。
Example:
Input: prices = [3,3,5,0,0,3,1,4] Output: 6（第 4 天買 0、第 6 天賣 3，賺 3；第 7 天買 1、第 8 天賣 4，賺 3）
Input: prices = [1,2,3,4,5] Output: 4（一筆交易買 1 賣 5；第二筆用不上）
Intuition
TIP
核心思路：用四個狀態變數依序遞推——第一次買、第一次賣、第二次買、第二次賣，每天更新到最佳。
buy1：完成第一次買後的最大「現金」（負成本）sell1：完成第一次賣後的最大利潤buy2：在sell1的基礎上再買的最大現金sell2：完成第二次賣後的最大利潤 → 答案- 同一天依序更新，允許「當天買當天賣」不影響正確性（利潤 0）
Approaches
1. 2D DP (transactions × holding) — O(n·k) / O(n·k)
- Idea:
dp[i][j][持股]表示前 i 天、用了 j 次交易、是否持股的最大利潤（k = 2） - Time:
O(n·k)- k = 2 - Space:
O(n·k)
class Solution {
fun maxProfit(prices: IntArray): Int {
val n = prices.size
if (n == 0) return 0
val k = 2
// hold[j] / cash[j]：用了 j 次交易、持股 / 不持股的最大利潤
val hold = IntArray(k + 1) { Int.MIN_VALUE }
val cash = IntArray(k + 1)
for (p in prices) {
for (j in 1..k) {
hold[j] = maxOf(hold[j], cash[j - 1] - p) // 第 j 次買
cash[j] = maxOf(cash[j], hold[j] + p) // 第 j 次賣
}
}
return cash[k]
}
}⭐ 2. Four Rolling State Variables — O(n) / O(1)
- Idea: k = 2 時直接展開成四個變數，省去陣列
- Time:
O(n)- 掃描一次 - Space:
O(1)
class Solution {
fun maxProfit(prices: IntArray): Int {
var buy1 = Int.MIN_VALUE; var sell1 = 0
var buy2 = Int.MIN_VALUE; var sell2 = 0
for (p in prices) {
buy1 = maxOf(buy1, -p) // 第一次買：花 p
sell1 = maxOf(sell1, buy1 + p) // 第一次賣
buy2 = maxOf(buy2, sell1 - p) // 用第一次的利潤再買
sell2 = maxOf(sell2, buy2 + p) // 第二次賣 → 答案
}
return sell2
}
}🔑 Takeaways
- Pattern: 狀態機 DP——以「交易次數 × 是否持股」為狀態，本題是 188（最多 k 次）的 k = 2 特例
- Key trick: 四變數依
buy1→sell1→buy2→sell2的順序在同一迴圈更新即可滾動成 O(1)。先理解這題再推廣到 188 會很順