因为暴力枚举所有子数组时间复杂度为O(n²)，对10⁵规模数组必超时；Kadane算法以O(n)时间和O(1)空间求解，核心是状态转移：以i结尾的最大和等于max(nums[i], 前一状态+nums[i])，且需用首元素初始化避免全负数错误。
为什么直接用 Kadane 算法而不是暴力枚举
暴力枚举所有子数组需要 O(n²) 时间，对 10⁵ 长度的数组会超时；Kadane 是唯一能稳定做到 O(n) 的通用解法，且空间仅需 O(1)。它不依赖前缀和预处理，也不要求数组有特殊性质（比如全为整数就足够）。
核心思想是：以每个位置结尾的最大子数组和，要么是“前面已知最大和 + 当前数”，要么是“从当前数重新开始”。这个决策只看上一步结果，无需回溯。
Kadane 算法的标准实现与边界处理
标准写法容易在全负数数组上出错——比如 [-5, -2, -8]，正确答案是 -2，但若初始化 max_ending_here 为 0 就会返回 0。
- 必须用数组首元素初始化
max_so_far和max_ending_here，不能设为 0 或INT_MIN后再进循环（后者会导致空数组误判） - 循环从下标 1 开始，每次更新：
max_ending_here = max(nums[i], max_ending_here + nums[i]) - 同步更新
max_so_far = max(max_so_far, max_ending_here)
int maxSubArray(vector<int>& nums) {
int max_so_far = nums[0];
int max_ending_here = nums[0];
for (int i = 1; i < nums.size(); ++i) {
max_ending_here = max(nums[i], max_ending_here + nums[i]);
max_so_far = max(max_so_far, max_ending_here);
}
return max_so_far;
}想同时返回子数组区间？改两行就行
原算法只关心最大和，但实际调试或业务中常需知道起止下标。只需额外记录 start、end 和临时起点 temp_start：
立即学习“C++免费学习笔记（深入）”；
- 当
nums[i] > max_ending_here + nums[i]成立，说明要重开子数组，此时temp_start = i - 当
max_so_far被更新，就同步更新start = temp_start和end = i - 注意：
start和end是闭区间，返回时可直接用vector<int>(nums.begin()+start, nums.begin()+end+1)</int>
遇到浮点数或大整数怎么办
Kadane 本身不限制数值类型，但要注意溢出和精度：
- 若用
double，比较操作（如max(a,b)）仍安全，但累加可能丢失精度；建议改用long double或定点运算 - 若元素是
long long且范围接近LLONG_MAX，加法可能溢出，需在相加前检查：if (max_ending_here > 0 && nums[i] > LLONG_MAX - max_ending_here)则强制重开 - STL 的
max对自定义类型需重载，别直接套用 <code>std::max而不确认比较逻辑
最易被忽略的是：算法假设数组非空。传入空 vector 时，第一行 nums[0] 会越界——调用前务必加 if (nums.empty()) throw runtime_error("empty array") 或约定返回 0 / 特殊值。
