LeetCode Maximum Subarray：Kadane 算法 O(n) 與分治法 O(n log n) 完整解析

問題描述

給定整數數組（含正負），找出連續子數組的最大和。至少包含一個元素。
例：[-2,1,-3,4,-1,2,1,-5,4] → 最大和 6（子數組 [4,-1,2,1]）。

方法一：動態規劃 / Kadane 算法 O(n)

狀態定義：dp[i] = 以 i 結尾的最大子數組和。
遞推：dp[i] = max(nums[i], dp[i-1] + nums[i])
若前綴和 dp[i-1] < 0，拋棄前綴，從當前元素重新開始。
答案：max(dp[i])。

空間優化：只需兩個變量 cur, ans。

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;
}

方法二：分治法 O(n log n)

將數組分為左右兩半，最大子數組三種情況：

1. 完全在左半部 → 遞歸求解
2. 完全在右半部 → 遞歸求解
3. 跨越中點 → 從中點向左求最大後綴和，向右求最大前綴和，相加加上中點值

取三者最大值。

int maxSub(vector& nums, int l, int r) {
    if (l > r) return INT_MIN;
    int m = (l + r) >> 1;
    int lMax = maxSub(nums, l, m-1);
    int rMax = maxSub(nums, m+1, r);
    int lSum = 0, lBest = 0;
    for (int i = m-1; i >= l; i--) {
        lSum += nums[i];
        lBest = max(lBest, lSum);
    }
    int rSum = 0, rBest = 0;
    for (int i = m+1; i <= r; i++) {
        rSum += nums[i];
        rBest = max(rBest, rSum);
    }
    return max({lMax, rMax, lBest + rBest + nums[m]});
}
int maxSubArray(vector& nums) {
    return maxSub(nums, 0, nums.size()-1);
}

複雜度對比

擴展：輸出最大子數組區間

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;
}

總結

Maximum Subarray 是動態規劃入門「Hello World」。Kadane 算法以 cur = max(nums[i], cur + nums[i]) 一行核心邏輯解決，O(n) 時間、O(1) 空間無懈可擊。分治法雖慢但展示了「跨越中點」的巧妙思想。面試首選 Kadane，並能手寫區間出版本。