經典面試題：最大子數組和（Kadane 算法）O(n) 完美解法

前言

希望大家把面試題當成純編程題享受思考樂趣，暫時放下面試包袱，潛心攻克。

題目

輸入整型數組（含正負），求連續子數組最大和，要求 O(n)。
例：1, -2, 3, 10, -4, 7, 2, -5 → 最大子數組 3, 10, -4, 7, 2，和為 18。

層層遞進分析

1. 暴力三層循環 O(N³)

遍歷所有 Sum[i...j]，三層循環累加，極其低效。

int MaxSum(int* A, int n) {
    int maximum = -INF, sum;
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) {
            sum = 0;
            for (int k = i; k <= j; k++) sum += A[k];
            if (sum > maximum) maximum = sum;
        }
    return maximum;
}

2. O(N) 動態規劃 / 貪心核心邏輯

維護兩個變量：
b — 以當前元素結尾的最大子數組和
sum — 全局最大和

int maxSum(int* a, int n) {
    int sum = 0, b = 0;
    for (int i = 0; i < n; i++) {
        if (b <= 0) b = a[i];      // 前面累加拖後腿，重新開始
        else        b += a[i];      // 繼續累加
        if (sum < b) sum = b;       // 更新全局最大
    }
    return sum;
}

演示過程（以例數組）：

b  : 0  1 -1  3 13  9 16 18  7
sum: 0  1  1  3 13 13 16 18 18

核心：b <= 0 時捨棄前序，sum 記錄歷史峰值。

3. 處理全負數情況

上述代碼全負數返回 0，若需返回最大負數，初始化 sum = a[0]、b = a[0]，判斷條件改為 if (sum >= 0) sum += a[i]; else sum = a[i];。

int maxsum(int a[], int n) {
    int max = a[0], sum = 0;
    for (int j = 0; j < n; j++) {
        if (sum >= 0) sum += a[j];
        else          sum = a[j];
        if (sum > max) max = sum;
    }
    return max;
}

測試 {-1,-2,-3,-4} 返回 -1，正確。

總結

一維 DP / 貪心思想：只需單次掃描，維護「以此結尾的最優」與「全局最優」，時間 O(n)、空間 O(1)，極其優雅。