---
title: "53. Maximum Subarray"
url: "https://laigary.com/interview/coding/53-maximum-subarray"
type: "note"
section: "coding"
date: "2023-01-28"
updated: "2026-07-28"
tags: ["Greedy", "Dynamic Programming", "Array", "Classic"]
---

# 53. Maximum Subarray

[53\. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)

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

## 思路

### 狀態怎麼定義

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

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

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

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

**「把結尾（或起點）釘死來讓狀態可遞推」是子陣列 / 子序列類 DP 的通用手法**，[300. Longest Increasing Subsequence](/interview/coding/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](/interview/coding/134-gas-station) 是同一件事** —— 那題是「這一段撐不住就從下一站重新開始」。兩題一起看會很有感，差別只在 53 要的是過程中的最大值、134 要的是「最後一次重來的位置」。

## 解題方向

### 暴力解

```python
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]`）起手才對。**初始值代表的是「什麼都還沒選時的語意」**，選錯就等於偷偷放寬了題目條件。

### 自頂向下

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

```python
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)` 這種單一狀態上，這題卻**散在所有狀態裡**。

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

```python
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](/interview/coding/337-house-robber-iii) 回傳 `(偷, 不偷)` 是同一個手法。第一項負責往上遞推，第二項負責記全域最大值。

### 自底向上

```python
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]`，所以整個陣列可以塌成一個變數：

```python
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](/interview/coding/134-gas-station)（油量變負就換起點）。兩題的程式碼放在一起看：

```python
# 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](/interview/coding/300-longest-increasing-subsequence)（`dp[i]` 是以 `i` 結尾的最長遞增子序列）、[152. Maximum Product Subarray](/interview/coding/152-maximum-product-subarray)（乘積版，因為負負得正所以要同時維護最大和最小兩個狀態 —— 值得對照，它示範了「狀態不夠時要加維度」）。

整理見 [Dynamic Programming 模板](/interview/coding/dynamic-programming-template)。

## 複雜度

**自頂向下（記憶化）**
- 時間 $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]` → 滾成兩個變數**，三步剛好對應上面三種寫法。