題目描述

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

動態規劃核心思想

設 sum[i] 為以 i 結尾的最大子數組和。轉移：

• 若 sum[i-1] ≥ 0：延伸前一子數組，sum[i] = sum[i-1] + A[i]
• 若 sum[i-1] < 0：另起爐灶，sum[i] = A[i]

遍歷過程中維護全局最大值 maxSum。

代碼實現

int maxSubArray(int A[], int n) {
    if (n <= 0) return 0;
    int sum = 0;
    int maxSum = INT_MIN;
    for (int i = 0; i < n; i++) {
        sum += A[i];
        if (sum > maxSum) maxSum = sum;
        if (sum < 0) sum = 0; // 關鍵：負和歸零，另起爐灶
    }
    return maxSum;
}

關鍵點解析

• sum 累加當前元素
• maxSum 記錄歷史最大值（初始 INT_MIN 處理全負數組）
• sum < 0 時歸零：負數前綴只會拖累後續和，捨棄之
• 全負數組時：每個元素單獨成陣，maxSum 會捕獲最大的負數（最接近 0）

複雜度

• 時間：O(n) 單次遍歷
• 空間：O(1) 常數變量

擴展：輸出具體子數組

額外記錄 start, end 索引：當 sum < 0 重置時更新 start = i+1；當 maxSum 更新時記錄 end = i。

分治法對比（O(n log n)）

分治：最大子數組或在左半、或在右半、或跨中間。跨中間需從中間向兩邊擴展求最大前綴/後綴和。Kadane 算法更簡單高效。