53. Maximum Subarray

📘 題目敘述

給你一個整數陣列 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/