C++ 求最大子數組和：暴力 O(n³) 與 Kadane 算法 O(n) 對比

問題描述

給定整數數組（含正負），找出連續子數組的最大和。例如 {2,3,4,5,6,7,8,-22,1} 最大子數組和為 35（前 7 個元素）。

方法一：三層循環暴力 O(n³)

int getmaxsum(int a[], int n) {
    int save = 0;
    for (int i = 0; i <= n; i++)           // 右端點
        for (int j = 0; j < i; j++)        // 左端點
            for (int k = j; k < i; k++)    // 求和
                sum += a[k];
            save = max(save, sum);
            sum = 0;
    }
    return save;
}

缺點：三層循環，n=1000 即 10⁹ 次操作，極慢。

方法二：Kadane 算法（動態規劃）O(n)

核心思想：維護 cur = 以當前元素結尾的最大子數組和。
遞推：cur = max(a[i], cur + a[i])。
若 cur < 0，拋棄前綴，從當前元素重新開始。
全局最大值 ans = max(ans, cur)。

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

代碼對比

Kadane 算法擴展：輸出子數組區間

int maxSubArray(vector& nums, int& L, int& R) {
    int cur = nums[0], ans = nums[0];
    int curL = 0;
    L = R = 0;
    for (int i = 1; i < nums.size(); i++) {
        if (cur + nums[i] < nums[i]) {
            cur = nums[i];
            curL = i;
        } else {
            cur += nums[i];
        }
        if (cur > ans) {
            ans = cur;
            L = curL;
            R = i;
        }
    }
    return ans;
}

分治法 O(n log n) 备选

將數組分為左右兩半，最大子數組或在左、或在右、或跨越中點。跨越中點部分從中點向兩側延伸求最大前綴/後綴和。遞歸求解。雖然比 Kadane 慢，但展示了分治思想。

總結

最大子數組和是動態規劃入門經典。Kadane 算法以 O(n) 時間、O(1) 空間完美解決，核心是「若前綴和為負則拋棄」。面試與競賽必會，務必熟練掌握並能手寫無誤。