# 53. Maximum Subarray

**練習日期：** 2026-02-10
**難度：** Medium
**類型：** Array、Prefix Sum

## 📘 題目敘述

給你一個整數陣列 `nums`，請找出具有最大總和的**連續子陣列**（至少包含一個元素），並回傳這個最大總和。

### 條件限制

* `1 <= nums.length <= 10^5`
* `-10^4 <= nums[i] <= 10^4`

## 🧠 解題思路（一）前綴和

我的想法是用**前綴和**把「任意一段子陣列的總和」快速算出來。

我先建立一個前綴和陣列 `sum`，讓：

* `sum[0] = 0`
* `sum[t] = nums[0] + nums[1] + ... + nums[t-1]`

這樣一來，任何連續子陣列 `nums[j ... k-1]` 的總和就可以用：

`sum[k] - sum[j]`

所以我就把所有可能的 `(j, k)` 都枚舉一次，找最大的 `sum[k] - sum[j]`，更新到 `ans`。

這份寫法的重點是：
前綴和讓子陣列總和的計算變成 O(1)，但我仍然用雙迴圈枚舉所有區間，所以總時間會是 O(n^2)。

### 所有變數

* `nums`：題目輸入陣列
* `sum`：前綴和陣列，`sum[t]` 代表前 `t` 個元素的總和
* `ans`：目前找到的最大子陣列總和

## 🪜 主要流程步驟（一）

### 1. 建立前綴和陣列 `sum`

* 先放一個 `0` 當作起點，表示「前 0 個元素總和」
* 依序把 `nums[i]` 加到 `sum.back()`，得到新的前綴和並 push 進 `sum`
* 建完後 `sum` 長度會是 `nums.size() + 1`

### 2. 枚舉所有子陣列，用 `sum[k] - sum[j]` 算總和

* `j` 從 `0` 走到 `sum.size() - 2`
* `k` 從 `j + 1` 走到 `sum.size() - 1`
* 這樣 `(j, k)` 就代表一段非空子陣列
* 用 `sum[k] - sum[j]` 得到該段子陣列總和，並用它更新 `ans`

### 3. 回傳答案

* 雙迴圈跑完後，`ans` 就是最大連續子陣列總和

## 💻 程式碼實作（一）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 1) {
            return nums[0];
        }
        vector<int> sum = {0};
        int ans = INT_MIN;
        for (int i = 0; i < nums.size(); i++) {
            sum.push_back(nums[i] + sum.back());
        }
        for (int j = 0; j < sum.size() - 1; j++) {
            for (int k = j + 1; k < sum.size(); k++) {
                ans = max(ans, sum[k] - sum[j]);
            }
        }
        return ans;
    }
};

## 🧠 解題思路（二）DP

這題我用的是很直觀的 DP 思考：

> **我走到某個位置時，我要嘛把它接在前面的子陣列後面，要嘛從這裡重新開一段。**
> 哪一個比較好？看「前面的累積和是不是負的」。

我用 `now` 表示「目前這段連續子陣列的總和」，也就是我正在維護的一段候選解。

當我遇到下一個數字 `i`：

* 如果 `now < 0`，代表我目前這段的總和是負的
那把它接下去只會拖累未來的總和，所以我乾脆放棄它，改成從 `i` 重新開始一段：`now = i`
* 如果 `now >= 0`，代表目前這段總和是正的（或至少不負）
那接上 `i` 只會讓總和更大，所以直接累加：`now += i`

接著我用 `best` 來記錄「目前為止看過的最大子陣列總和」，每走一步就更新一次 `best = max(best, now)`。

這樣一次掃描就能得到答案。

### 所有變數

* `now`：目前正在累積的連續子陣列總和（以「結尾在當前元素」的角度來看）
* `best`：目前為止的最大子陣列總和（最後回傳它）

## 🪜 主要流程步驟（二）

### 1. 初始化 now 與 best

* `now` 初始化成很小（`INT_MIN`），表示還沒開始累積
* `best` 也初始化成很小，表示答案還沒被更新過

### 2. 從左到右掃描每個元素，決定要不要重開一段

每遇到一個元素 `i`：

* 如果 `now < 0`
代表前面那段是負貢獻，直接丟掉，從 `i` 開始：`now = i`
* 否則
代表前面那段不會拖累，接著加：`now += i`

### 3. 每一步都更新 best

* `best = max(best, now)`
* 代表我把「到目前為止所有可能連續子陣列的最大值」都記下來

### 4. 回傳 best

掃描完後 `best` 就是最大連續子陣列總和。

## 💻 程式碼實作（二）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int now = INT_MIN, best = INT_MIN;
        for (int i : nums) {
            if (now < 0) {
                now = i;
            } else {
                now += i;
            }
            best = max(best, now);
        }
        return best;
    }
};

## 🔗 題目連結
https://leetcode.com/problems/maximum-subarray/description/