LeetCode 53 Maximum Subarray：動態規劃 O(n) 最大子數組和

題目回顧

找出數組中連續子數組的最大和（至少一個元素）。
例：[-2,1,-3,4,-1,2,1,-5,4] → [4,-1,2,1] 和 = 6

Kadane 算法（動態規劃）

dp[i]：以 i 結尾的最大子數組和。
遞推：dp[i] = max(nums[i], dp[i-1] + nums[i])
即：若前綴和 dp[i-1] ≤ 0，拋棄重開；否則延續。
答案 = max(dp)。

C++ 代碼（空間優化）

class Solution {
public:
    int maxSubArray(vector& nums) {
        int maxSum = nums[0], curSum = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            curSum = max(nums[i], curSum + nums[i]);
            maxSum = max(maxSum, curSum);
        }
        return maxSum;
    }
};

分治法（O(n log n)）

分左右半部，最大子數組要么在左、要么在右、要么跨中間。跨中間部分需從中間向兩邊掃描最大前綴/後綴和。

複雜度

• DP：O(n) 時間，O(1) 空間
• 分治：O(n log n) 時間，O(log n) 空間

總結

最大子數組和是動態規劃入門經典。「棄負留正」的貪心直覺經 DP 證明為最優。面試必會，可延伸至「最大子矩陣和」（二維前綴和 + 枚舉行對壓縮為一維）。