53. Maximum Subarray

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

53. Maximum Subarray

找出連續子陣列裡總和最大的那一個，回傳那個總和。子陣列至少要有一個元素。

思路

狀態怎麼定義

直覺會想定義成「前 i 個元素裡的最大子陣列和」，但這樣推不下去 —— 知道前 i 個的答案，沒辦法決定第 i+1 個能不能接上去，因為不知道那個答案的子陣列有沒有頂到位置 i。

正確的定義要把「結尾」釘死：

dp[i] = 以第 i 個元素結尾的最大子陣列和

這樣就接得下去了，因為「以 i 結尾」明確告訴你第 i 個一定在裡面。最後答案是 max(dp)（枚舉所有可能的結尾）。

「把結尾（或起點）釘死來讓狀態可遞推」是子陣列 / 子序列類 DP 的通用手法，300. Longest Increasing Subsequence 也是同一招。

每一步只有兩個選擇

這題的想法是，我不斷的計算出當前位置前一直到現在的所有元素的總和：如果說總和比當下的值小，那代表當前位置的子陣列總和應該就要用當下的值；如果說總和比當下的值大，那就代表可以有更大的最大子陣列。

換句話說，站在第 i 個元素，我只要回答一個問題：

前面那一段，對我來說是加分還是扣分？

• 加分（dp[i-1] > 0）→ 接上來，dp[i] = nums[i] + dp[i-1]
• 扣分（dp[i-1] <= 0）→ 丟掉，從我自己重新開始，dp[i] = nums[i]

寫成一行就是 max(nums[i], nums[i] + dp[i-1])。

這個「累積量變成負擔就歸零重來」的動作，和 134. Gas Station 是同一件事 —— 那題是「這一段撐不住就從下一站重新開始」。兩題一起看會很有感，差別只在 53 要的是過程中的最大值、134 要的是「最後一次重來的位置」。

解題方向

暴力解

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:

        ans = float('-inf')
        for end in range(1, len(nums)+1):
            for start in range(end):
                local = 0
                for i in range(start, end):
                    local += nums[i]
                ans = max(ans, local)
        return ans

ans 的初始值不能是 0。 這是這題最經典的坑：寫 ans = 0 等於預設「空子陣列」也是合法答案，但題目要求至少一個元素。全部都是負數時正解是「最大的那個負數」，用 0 起手就會回傳 0。

[-1] 應該回 -1、[-3, -2, -5] 應該回 -2，用 ans = 0 全部會變成 0。

用 float('-inf')（或 nums[0]）起手才對。初始值代表的是「什麼都還沒選時的語意」，選錯就等於偷偷放寬了題目條件。

自頂向下

直接把上面的遞推式翻成遞迴：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        @cache
        def dp(i):
            if i == 0:
                return nums[0]
            return max(nums[i], nums[i] + dp(i - 1))

        return max(dp(i) for i in range(len(nums)))

注意答案不是 dp(n-1)。dp(i) 是「以 i 結尾」的答案，而真正的答案可能結束在任何位置，所以要對所有 i 取 max。

這是這題和大多數 DP 題不一樣的地方：一般題目的答案就落在 dp(0) 或 dp(n) 這種單一狀態上，這題卻散在所有狀態裡。

如果想讓答案回到單一狀態，就得讓遞迴回傳一對值：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)

        @cache
        def dp(i):
            # 回傳 (以 i 開頭的最大和, nums[i:] 裡任意位置的最大和)
            if i == n - 1:
                return (nums[i], nums[i])
            start_next, best_next = dp(i + 1)
            start_here = max(nums[i], nums[i] + start_next)
            return (start_here, max(start_here, best_next))

        return dp(0)[1]

一個值不夠組合，就回傳兩個 —— 和 337. House Robber III 回傳 (偷, 不偷) 是同一個手法。第一項負責往上遞推，第二項負責記全域最大值。

自底向上

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [float('-inf')] * len(nums)

        dp[0] = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(nums[i], nums[i] + dp[i - 1])

        return max(dp)

最後找出 dp 中的最大值就好 —— 因為 dp[i] 是「以 i 結尾」的答案，真正的答案可能結束在任何位置。

dp[0] = nums[0] 這個起手同時也把「全負」的情況處理掉了，所以這一版不像暴力解那樣有初始值的坑。

Kadane：滾成 $O(1)$ 空間

dp[i] 只用到 dp[i-1]，所以整個陣列可以塌成一個變數：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curr = ans = nums[0]
        for num in nums[1:]:
            curr = max(num, curr + num)   # 前面那段加分就接上，扣分就丟掉
            ans = max(ans, curr)
        return ans

curr 是「以目前這個元素結尾」的最大和，ans 記全程看過的最大值。兩個變數必須分開 —— curr 會為了接下去而歸零重來，但 ans 一旦記住的最大值就不能掉。這是 Kadane 演算法，也是這題的標準答案。

補充

還有一個 $O(n\log n)$ 的分治解法，LeetCode 的 follow-up 明講了：把陣列切兩半，答案要嘛完全在左半、要嘛完全在右半、要嘛跨過中線（從中線往左取最大後綴 + 往右取最大前綴）。我沒有用這個角度寫過這題，所以這裡不展開；它比 Kadane 慢，價值在於它能推廣到「線段樹上維護區間最大子陣列和」那類需要支援更新的變形。

同一個「歸零重來」手法：134. Gas Station（油量變負就換起點）。兩題的程式碼放在一起看：

# 53:  前面那段對我沒幫助就丟掉，從我自己重新開始
curr = max(num, curr + num)

# 134: 這一段撐不住就丟掉，從下一站重新開始
if fuel + gas[i] - cost[i] < 0:
    start = i + 1
    fuel = 0

遞迴深度取決於「你先問哪個狀態」

上面兩個自頂向下的版本，遞迴深度理論上都是 n，而 LeetCode 這題的 n 上限是 ${10}^5$ —— 遠超過 Python 預設的 recursionlimit = 1000。但兩種問法的行為不一樣（以 n = 5000、預設上限為例）：

怎麼問	結果
max(dp(i) for i in range(n))（由小到大）	沒爆
dp(n - 1)（直接問最後一個）	RecursionError

同一份 dp(i)，只差在先問哪一個狀態。

原因是那個 for 迴圈其實在由下往上暖 cache：dp(0) 是 base case 深度 1；dp(1) 呼叫 dp(0) 時已經命中 cache，深度只有 2；dp(2) 同理⋯⋯整個過程的遞迴深度從沒超過 2。

而回傳一對值的那版，dp(0) 必須先算 dp(1)、dp(1) 又要 dp(2)⋯⋯一路遞迴到底才碰到第一個 base case，深度就是 n，所以 n = 5000 就爆了。

所以第一版之所以安全是個副作用，不是它本質上比較好 —— 改寫成 return dp(len(nums) - 1) 就會炸。加 @cache 本來就是 DP 的標準手法，只是遇到很大的 n 時要意識到深度這件事。

同一類「釘死結尾」的 DP：300. Longest Increasing Subsequence（dp[i] 是以 i 結尾的最長遞增子序列）、152. Maximum Product Subarray（乘積版，因為負負得正所以要同時維護最大和最小兩個狀態 —— 值得對照，它示範了「狀態不夠時要加維度」）。

整理見 Dynamic Programming 模板。

複雜度

自頂向下（記憶化）

• 時間 $O(n)$ — 每個狀態只算一次
• 空間 $O(n)$ — cache 加上遞迴堆疊（深度視問法而定，見補充）

暴力解

• 時間 $O(n^3)$ — 兩層迴圈枚舉起訖，第三層重新加總；把內層改成累加可以降到 $O(n^2)$
• 空間 $O(1)$

自底向上

• 時間 $O(n)$ — 一趟迴圈
• 空間 $O(n)$ — dp 陣列

Kadane

• 時間 $O(n)$ — 一趟
• 空間 $O(1)$ — 兩個變數

其中 n 是陣列長度。

Kadane 是這題的最佳解。優化的路徑是：暴力 → 釘死結尾的 dp[i] → 滾成兩個變數，三步剛好對應上面三種寫法。