尋找數組中連續子數組的最大和。本文詳解 **Kadane 算法** 核心思想：以 `dp[i]` 表示以 `i` 結尾的最大子數組和，狀態轉移 `dp[i] = max(nums[i], dp[i-1] + nums[i])`，空間優化為 O(1)，並分析全負數邊界、分治法對比與變體擴展。
`dp[i]` = 以索引 `i` 結尾的連續子數組的最大和。
兩種選擇：
取最大：`dp[i] = max(nums[i], dp[i-1] + nums[i])`。
答案 = `max(dp[0..n-1])`。
只需保留 `dp[i-1]`（即 `cur_max`）和全局最大 `global_max`。
#include // INT_MIN
int maxSubArray(int* nums, int numsSize) {
int cur_max = nums[0];
int global_max = nums[0];
for (int i = 1; i < numsSize; i++) {
// 狀態轉移：延續還是重新開始
cur_max = (cur_max > 0) ? cur_max + nums[i] : nums[i];
// 等價：cur_max = fmax(cur_max + nums[i], nums[i]);
// 更新全局最大
if (cur_max > global_max) global_max = cur_max;
}
return global_max;
}
分治：最大子數組在左半、右半、或跨中間。跨中間需從中向左/右掃描最大前/後綴和。時間 O(n log n)，空間 O(log n) 遞歸棧。Kadane O(n) 完勝。
| 變體 | 修改點 |
|---|---|
| 返回子數組索引 [l, r] | 記錄 `cur_max` 更新時的起始索引，`global_max` 更新時的最佳區間 |
| 環形數組最大子數組和 | 答案 = max(普通最大和, 總和 - 最小子數組和) （排除全負數情況） |
| 最大子矩陣和 (2D) | 枚舉上下行邊界，壓縮列和為 1D 數組，套用 Kadane → O(n³) |
| k 不相交最大子數組和 | DP[i][k] = max(DP[i-1][k], max_j(DP[j-1][k-1] + sum(j..i))) → O(n²k) 可優化 |
[-2,1,-3,4,-1,2,1,-5,4] → 6 (子數組 [4,-1,2,1])
[1] → 1
[5,4,-1,7,8] → 23
[-2,-1] → -1
[-1,-2,-3] → -1
[0,-1,0] → 0
最大子數組和是**動態規劃入門神題**，Kadane 算法以「局部最優推導全局最優」的優雅邏輯，實現 O(n) 時間 O(1) 空間極致優化。掌握「狀態定義 `dp[i]`、轉移方程 `max(nums[i], dp[i-1]+nums[i])`、滾動優化、全負數初始化」四大核心，即可舉一反三解決子數組/子矩陣/不相交子數組等系列進階問題。
