最大子數組和：Kadane 算法與四種實現的完整解析

問題描述

給定整數數組（含正負），找出連續子數組的最大和。要求 O(n)。
例：[1, -2, 3, 10, -4, 7, 2, -5] → 最大子數組 [3, 10, -4, 7, 2]，和 = 18。

算法演進

1. 三層暴力 O(n³)

枚舉所有 [i,j] 區間，內層求和。教學用，不可用。

2. 兩層優化 O(n²)

固定左端，右擴累加和。仍太慢。

3. 分治法 O(n log n)

最大子數組或在左半、或在右半、或跨中間。遞歸求解。
《算法導論》經典，但非最優。

4. 動態規劃 / Kadane 算法 O(n) —— 最優解

狀態定義：dp[i] = 以 a[i] 結尾的最大子數組和。
轉移：dp[i] = max(a[i], dp[i-1] + a[i])
答案：max(dp[i])

空間優化至 O(1)：只需兩變量 cur、ans。

處理全負數組

• 若允許空子數組 → 返回 0，初始 cur=0, ans=0
• 若要求非空 → 初始 cur=ans=a[0]，循環從 1 開始

四種 C++ 實現

版本 A：標準 Kadane（返回最大和，全負返回最大負數）

int maxSubArray(const vector<int> &a) {
    int cur = a[0], ans = a[0];
    for (size_t i = 1; i < a.size(); ++i) {
        cur = max(a[i], cur + a[i]);
        ans = max(ans, cur);
    }
    return ans;
}

版本 B：允許空子數組（全負返回 0）

int maxSubArrayAllowEmpty(const vector<int> &a) {
    int cur = 0, ans = 0;
    for (int x : a) {
        cur = max(0, cur + x);
        ans = max(ans, cur);
    }
    return ans;
}

版本 C：同時輸出子數組區間 [L, R]

pair<int, int> maxSubArrayRange(const vector<int> &a) {
    int cur = a[0], ans = a[0];
    int curL = 0, bestL = 0, bestR = 0;
    for (size_t i = 1; i < a.size(); ++i) {
        if (cur + a[i] < a[i]) { // 重新開始
            cur = a[i];
            curL = i;
        } else {
            cur += a[i];
        }
        if (cur > ans) {
            ans = cur;
            bestL = curL;
            bestR = i;
        }
    }
    return {bestL, bestR};
}

版本 D：《Data Structures and Algorithm Analysis in C》原書四種實現對比

書中給出：三層暴力、兩層優化、分治、線性掃描。線性掃描即 Kadane 核心邏輯：

// 書中 Algorithm 4
int maxSubSum(const int a[], int n) {
    int maxSum = 0, thisSum = 0;
    for (int i = 0; i < n; ++i) {
        thisSum += a[i];
        if (thisSum > maxSum) maxSum = thisSum;
        else if (thisSum < 0) thisSum = 0;
    }
    return maxSum; // 全負返回 0
}

擴展問題

1. 二維矩陣最大子矩陣和：枚舉上下行邊界，將列壓縮為 1D 數組，套用 1D 算法 → O(rows² × cols)
2. 最大子數組乘積：維護 maxEndingHere 和 minEndingHere（負負得正）
3. 環形數組最大子數組和：max(普通最大和, 總和 - 最小子數組和)，注意全負情況

總結

最大子數組和是動態規劃入門經典，Kadane 算法以極簡代碼實現最優複雜度，展現了「狀態轉移+空間壓縮」的 DP 精髓。工程中處理流式數據、尋找最優區間、信號處理等場景廣泛應用。