最大子序列和問題：從 O(n³) 到 O(n) 的四重算法演進與工程選型

前言

最大子序列和問題 是《編程珠玑》經典案例：給定整數序列 (含正負)，找出連續子數組的最大和。本文展示四種算法演進——三層暴力 O(n³)、二層優化 O(n²)、分治 O(n log n)、掃描線 O(n)，附 Java 實現、複雜度證明、工程場景選型指南。

問題形式化

輸入：數組 a[0..n-1]，元素可正可負。
輸出：max{ Σ a[i..j] | 0 ≤ i ≤ j < n }。
約定：空子數組和為 0 (全負時返回 0)；若要求非空，初始值設為 Integer.MIN_VALUE。

算法一：三層暴力枚舉 O(n³)

枚舉所有 i ≤ j，內層求和。

public static int maxSubArrayV1(int[] a) {
    int maxSum = 0;
    for (int i = 0; i < a.length; i++) {
        for (int j = i; j < a.length; j++) {
            int sum = 0;
            for (int k = i; k <= j; k++) sum += a[k]; // 重複累加
            maxSum = Math.max(maxSum, sum);
        }
    }
    return maxSum;
}

缺陷：sum 重複計算，k 循環可提至 j 循環外。

算法二：二層優化 O(n²)

固定左端點 i，右端點 j 右擴時增量累加。

public static int maxSubArrayV2(int[] a) {
    int maxSum = 0;
    for (int i = 0; i < a.length; i++) {
        int sum = 0;
        for (int j = i; j < a.length; j++) {
            sum += a[j];          // O(1) 更新
            maxSum = Math.max(maxSum, sum);
        }
    }
    return maxSum;
}

進步：消除內層求和循環，但仍需枚舉所有起點。

算法三：分治法 O(n log n)

將數組分為左右兩半，最大子數組必屬於三種情況之一：

1. 完全在左半部
2. 完全在右半部
3. 跨越中點 (含中點左側後綴 + 右側前綴)

public static int maxSubArrayV3(int[] a, int l, int r) {
    if (l > r) return 0;
    if (l == r) return Math.max(0, a[l]);
    int m = (l + r) >> 1;
    // 跨越中點最大和
    int leftMax = 0, sum = 0;
    for (int i = m; i >= l; i--) { sum += a[i]; leftMax = Math.max(leftMax, sum); }
    int rightMax = 0; sum = 0;
    for (int i = m + 1; i <= r; i++) { sum += a[i]; rightMax = Math.max(rightMax, sum); }
    int crossMax = leftMax + rightMax;
    // 遞歸左右
    int leftAns = maxSubArrayV3(a, l, m);
    int rightAns = maxSubArrayV3(a, m + 1, r);
    return Math.max(crossMax, Math.max(leftAns, rightAns));
}

復雜度證明：T(n) = 2T(n/2) + O(n) → Master 定理 → O(n log n)。

算法四：Kadane 掃描算法 O(n) — 線性時空最優解

核心洞察：維護 maxEndingHere (以當前元素結尾的最大子數組和) 與 maxSoFar (全局最大)。若 maxEndingHere < 0，拋棄前綴，從下一元素重新開始。

public static int maxSubArrayV4(int[] a) {
    int maxEndingHere = 0, maxSoFar = 0;
    for (int x : a) {
        maxEndingHere = Math.max(maxEndingHere + x, 0); // 關鍵：歸零重啟
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}

變體：要求非空子數組：初始化 maxEndingHere = maxSoFar = a[0]；循環 maxEndingHere = Math.max(x, maxEndingHere + x)。

五、四算法綜合對比

六、工程落地擴展

1. 記錄區間位置：在 V4 中維護 start, end, tempStart 變量，更新 maxSoFar 時同步記錄。
2. 二維矩陣最大子矩陣和：枚舉上下行邊界 O(n²)，將列壓縮為一維數組調用 V4，總 O(n³)。
3. 環形數組最大子序列和：max(普通最大和, 總和 - 最小子數組和) (需處理全負情況)。
4. 流式/在線處理：V4 單遍歷、常數空間，天然支持流式輸入 (如網絡封包、傳感器數據)。

結語

最大子序列和問題完美展示了從暴力枚舉到動態規劃/貪心的算法提煉過程。Kadane 算法以 10 行代碼實現理論最優，是面試必考、工程必會的經典。理解其「局部最優決策導致全局最優」的貪心證明 (交換論證)，能啟發解決股票買賣、最大子矩陣、最大子段積等同構問題。