主題: 學習筆記

LeetCode 53：最大子陣列，從向左重算到保存上一輪結果

記錄我的 Maximum Subarray 解題過程，從 O(n²) 向左掃描改成 O(n)，解釋 endingHere 與 best 的差別、全負數邊界與可執行測試。

我最初固定目前的位置，再往左把每一段加起來，找出最大的和。這樣能直接對照題意，但陣列一長，重複計算就太多。

在 AI 提示與程式骨架協助下，我把內層 while 移掉，改成保存上一輪的結果。這篇保留我的初版與最後補完的版本，另外補上為什麼只留一個局部最佳值就夠，以及全負數時要注意的初始化。

題目

LeetCode 53：Maximum Subarray 要找出非空連續子陣列的最大總和，只回傳總和。元素必須相鄰，不能排序後再選，也不能跳過中間的負數。

例如 [-2,1,-3,4,-1,2,1,-5,4] 的答案為 6，對應 [4,-1,2,1]。輸入長度為 1 到 100000，元素介於 -10000 到 10000。本篇處理 O(n) 解法，不展開分治進階題。

我原本向左重算的版本

為了讓兩版能放在同一個檔案，這裡只將初版函式改名。

function maxSubArrayOriginal(nums: number[]): number {
    let max = nums[0];
    let minIndex = 0;
    for (let i = 0; i < nums.length; i++) {
        let sum = 0;
        let maxSum = nums[i];
        let j = i;
        let minIdx = 0;
        while (j >= minIndex) {
            sum += nums[j];
            if (sum >= maxSum) {
                maxSum = sum;
                minIdx = j;
            }
            j--;
        }
        if (maxSum > max) {
            max = maxSum;
            minIndex = minIdx;
        }
    }
    return max;
}

外層固定右端點 i，內層從 i 往左累加。我試著用 minIndex 縮小之後搜尋的範圍，但這無法保證每輪都省下足夠的工作。

若陣列全部是 1，每次往左加，總和都會變大，最後 minIdx 仍然回到 0。下一輪又從目前位置一路加到開頭，累計工作量就是 1 + 2 + ... + n，因此最差時間為 O(n²)，額外空間為 O(1)。

這裡不靠移動搜尋邊界來保證效能，也不把 minIndex 當成通用的剪枝規則。真正要省掉的是每一輪對各個起點的重新比較。

最後解法：只保存兩種最大值

下面是我依提示補完的最終版本。演算法沒有再另外替換。

function maxSubArray(nums: number[]): number {
    let endingHere = nums[0];
    let best = nums[0];
    for (let i = 1; i < nums.length; i++) {
        endingHere = Math.max(endingHere + nums[i], nums[i]);
        best = Math.max(endingHere, best);
    }
    return best;
}

兩個變數有不同的範圍：

• endingHere 是一定以目前位置結尾的最大總和。
• best 是截至目前為止，所有結尾位置中最大的總和。

endingHere 可以變小。它必須包含目前元素，不能繼續停在前一格。best 則可以保留先前的結果，不一定在目前位置結束。

為什麼只比較兩個選項

任何以 i 結尾的非空連續子陣列，只會是目前元素自己，或是一段以 i − 1 結尾的子陣列再接上目前元素。

如果選擇接上去，所有候選都會加同一個 nums[i]。原本比較小的總和，加上相同數字後仍然比較小，所以只需保留上一輪最大的那個。

因此：

endingHere = Math.max(上一輪 endingHere + nums[i], nums[i])

不是看到負數就丟掉。例如前段總和是 5，目前數字是 -1，接起來的 4 仍然比重新開始的 -1 大。但前段是 -3、目前數字是 4，重新開始的 4 就比接起來的 1 好。

更新局部結果後，再與歷史最大值比較：

best = Math.max(endingHere, best)

走一次例子

以 [-2,1,-3,4,-1,2,1,-5,4] 為例：

最後 endingHere 是 5，但答案仍是 6。若只回傳最後一輪的局部結果，就會漏掉中途出現的最大區間。

不變量與初始化

處理完位置 i 後，endingHere 等於所有以 i 結尾的非空連續子陣列總和的最大值；best 等於截至 i 為止所有非空連續子陣列的最大總和。

起點 i = 0 只有 [nums[0]] 可選，所以兩個變數都設為 nums[0]。之後根據前面的兩種選擇，能得到新的 endingHere，再更新 best。依序處理完整個陣列後，best 就涵蓋所有可能的結尾位置。

不要把 best 初始化成 0。[-3,-1,-2] 的答案是 -1，因為不能選空陣列。迴圈從 1 開始，則是因為第一個元素已經包含在初始狀態中。

複雜度與取捨

最後版本只走訪一次陣列，每輪固定次數的加法與比較，時間為 O(n)。只保存兩個數值與索引，額外空間為 O(1)，回傳結果也是單一數值。輸入陣列不會被修改。

它沒有保存每個位置的最佳值，也沒有記錄答案的起訖索引，因為題目只要總和。若未來要回傳區間，才需要另外追蹤起點及最佳區間的端點。

可執行測試與暴力解對照

把最終函式與以下程式放在同一個 TypeScript 檔案，在支援 TypeScript 的環境執行。暴力參考版不使用初版的搜尋邊界，直接枚舉所有連續區間，適合拿來比對小陣列。

import assert from "node:assert/strict";

assert.equal(maxSubArray([1]), 1);
assert.equal(maxSubArray([5, 4, -1, 7, 8]), 23);
assert.equal(maxSubArray([-1, 0]), 0);
assert.equal(maxSubArray([-3, -1, -2]), -1);
assert.equal(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]), 6);
assert.equal(maxSubArray([0, 0]), 0);
assert.equal(maxSubArray(new Array(100000).fill(1)), 100000);

function bruteForce(nums: number[]): number {
    let best = nums[0];
    for (let i = 0; i < nums.length; i++) {
        let sum = 0;
        for (let j = i; j < nums.length; j++) {
            sum += nums[j];
            best = Math.max(best, sum);
        }
    }
    return best;
}

let cases = 0;
for (let n = 1; n <= 6; n++) {
    for (let encoded = 0; encoded < 5 ** n; encoded++) {
        let value = encoded;
        const nums = Array.from({ length: n }, () => {
            const element = value % 5 - 2;
            value = Math.floor(value / 5);
            return element;
        });
        const before = [...nums];
        assert.equal(maxSubArray(nums), bruteForce(nums));
        assert.deepStrictEqual(nums, before);
        cases++;
    }
}
assert.equal(cases, 19530);

這段檢查包含單一元素、全負數、零、中間出現最大值，以及十萬個元素的輸入。另外用長度 1 到 6、元素為 -2 到 2 的 19530 組陣列，比對暴力參考版，並確認輸入沒有被修改。測試已執行通過；有限範圍測試不取代前面的正確性說明。

這次要記住的差別

我原本每輪都重新找「以目前位置結尾的最大和」。最後版本把這個結果留下來，下一輪只需決定要延續還是重新開始。

之後遇到類似題目，我要先分清楚局部狀態與歷史答案，並說明為什麼其他候選可以不保留。這比只記得少寫一層迴圈更有用。

參考資料

• LeetCode 53：Maximum Subarray：正式題意與輸入限制。
• Node.js assert：可執行斷言。