123. Best Time to Buy and Sell Stock III

──────────────────────────────────────────────────────────────────────

最多可以完成兩筆交易，求最大獲利。

思路

這一題改的旋鈕是「交易次數 = 2」。 完整的狀態機和其他五題的對照見股票買賣家族模板。

k = 2 是個尷尬的數字：比 121 的 1 多、又不像 122 的無限那樣可以把維度整個丟掉。所以貪心不能用了 —— 「把所有上漲區段吃下來」在只能交易兩次時是錯的。

因為只有兩次，可以把狀態機直接展開成四個變數，不必開陣列：

firstBuy    第一次買進後的最大獲利（是負的，因為只花錢還沒賺）
firstSell   第一次賣出後的最大獲利
secondBuy   第二次買進後的最大獲利
secondSell  第二次賣出後的最大獲利  ← 答案

關鍵是這條鏈的順序：secondBuy 是從 firstSell 出發的。也就是「第二次買進時，我口袋裡的錢是第一次交易賺完之後的餘額」。這一句話就是整題的核心：

𝑠𝑒𝑐𝑜𝑛𝑑𝐵𝑢𝑦 = \max (𝑠𝑒𝑐𝑜𝑛𝑑𝐵𝑢𝑦, 𝑓𝑖𝑟𝑠𝑡𝑆𝑒𝑙𝑙 - p r i c e)

把四個變數想成一條流水線，錢從 firstBuy 一路流到 secondSell，每一站都取「維持現狀」和「往前推進」的較大值。

為什麼可以在同一輪迴圈裡依序更新？ 因為 firstSell 用的是同一輪剛算好的 firstBuy，等於允許「今天買、今天賣」—— 那筆交易獲利 0，不會讓答案變大，所以無害。這個特性讓四行可以直接寫在一起。

解題方向

Final Profit = (Initial Profit - Buying Price) + Selling Price

這個式子是理解那條流水線的關鍵：每一次買進，都是從「上一階段累積的獲利」裡扣錢，而不是從 0 開始。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        firstBuy, firstSell = float('-inf'), 0
        secondBuy, secondSell = float('-inf'), 0

        for price in prices:
            firstBuy = max(firstBuy, -price)
            firstSell = max(firstSell, firstBuy + price)
            secondBuy = max(secondBuy, firstSell - price)
            secondSell = max(secondSell, secondBuy + price)

        return secondSell

firstBuy = max(firstBuy, -price) 是「從 0 出發買進」，所以是 -price；secondBuy = max(secondBuy, firstSell - price) 是「從第一次交易的獲利出發買進」。兩者的差別就是那條流水線。

兩個 Buy 都初始化成 -inf，因為「還沒開始就持有股票」不是合法狀態。

四行的順序不能亂：firstBuy → firstSell → secondBuy → secondSell，因為每一行都依賴上一行。

補充

這題也可以用 188. Stock IV 的通解跑 k=2，那是比較穩的作法 —— 四個變數的版本很漂亮，但一時想不起順序時，寫通解一定不會錯。

整個家族的對照見股票買賣家族模板。這題和 188 是同一組（k 有限），188 就是把這四個變數換成兩個長度 k 的陣列。

複雜度

時間 $O (n)$ — 一趟迴圈，每天做四次常數計算
空間 $O (1)$ — 只有四個變數

其中 n 是天數。

寫成 k=2 的通解則是 $O (n k) = O (2 n) = O (n)$ 時間、 $O (k) = O (1)$ 空間 —— 同一個量級，所以選哪一種只是可讀性的取捨，不影響效能。