122. Best Time to Buy and Sell Stock II

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

這個題目是每天都可以買賣股票，但是最多只能同時持有一股的股票，要買之前要先賣掉股票。

思路

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

k 無限帶來一個很好的簡化：狀態裡不需要記「還剩幾次」了 —— 因為「還剩無限次」和「用掉一次之後還剩無限次」是同一個狀態。所以 121 的三維狀態在這裡塌成兩個變數：手上有股票、手上沒股票。

還有一個更短的貪心解

因為次數無限，這題其實有一個一眼就能寫的解法：

把所有上漲的區段全部吃下來。

只要明天比今天貴，就今天買明天賣。看起來像作弊，但它是對的 —— 因為連續上漲 a → b → c 拆成兩筆交易 (b-a) + (c-b) 和一筆 (c-a) 獲利完全相同，而次數無限所以拆開不用付代價。下跌的區段則一律跳過（不參與，獲利 0）。

        return sum(max(0, prices[i] - prices[i-1]) for i in range(1, len(prices)))

面試時兩個都值得講：貪心版展示你看穿了題目的結構，DP 版展示你能推廣到其他五題。如果只給貪心解，面試官接著問 123（限兩次）就會卡住，因為貪心在有次數限制時不成立。

解題方向

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0

        buys = [float('-inf')] * len(prices) 
        sells = [0] * len(prices) 
        buys[0] = -prices[0]

        for i in range(1, len(prices)):
            buys[i] = max(buys[i-1], sells[i-1] - prices[i])
            sells[i] = max(sells[i-1], buys[i-1] + prices[i])

        return sells[-1]

兩行轉移就是狀態機的直譯：

buys[i]（今天結束時持有股票的最大獲利）= 昨天就持有，或昨天沒持有、今天買進
sells[i]（今天結束時不持有）= 昨天就不持有，或昨天持有、今天賣出

buys 初始化成 -inf 是哨兵：「第 0 天之前就持有股票」不是合法狀態，用 -inf 讓 max 自動淘汰它。

另一版把第 0 天的初始化搬進迴圈裡：

        for i in range(len(prices)):
            if i == 0:
                buys[i] = max(buys[i], 0 - prices[i])
            else:
                buys[i] = max(buys[i-1], sells[i-1] - prices[i])
            sells[i] = max(sells[i-1], buys[i-1] + prices[i])

兩種等價。兩個陣列其實都可以省掉，因為轉移只看前一天：

        buys, sells = float('-inf'), 0
        for price in prices:
            buys = max(buys, sells - price)
            sells = max(sells, buys + price)
        return sells

這裡有個看起來危險但其實無害的細節：sells 用的是同一輪剛更新過的 buys。等於允許「今天買、今天賣」，但那筆交易獲利是 0，不會讓答案變大 —— 所以結果仍然正確。（在 309 冷凍期那題就不能這樣偷懶了。）

補充

整個家族的對照見股票買賣家族模板。這題和 309、714 是同一組（都是 k 無限），差別只在多了冷凍期或手續費 —— 三題的程式碼幾乎一樣，值得一起看。

貪心能用的條件值得單獨記住：次數無限、沒有冷凍期、沒有手續費。加上任何一個限制，貪心就不成立，必須回到狀態機。

複雜度

動態規劃

時間 $O (n)$ — 一趟迴圈，每天常數次計算
空間 $O (n)$ 用陣列、 $O (1)$ 用滾動變數

貪心

時間 $O (n)$ — 一趟
空間 $O (1)$

其中 n 是天數。兩者同級，貪心的常數更小也更短，但只適用這一題。