Kadane算法用O(n)时间解决最大子数组和问题：max_ending_here表示以当前元素结尾的最大和，max_so_far记录全局最大值；二者不可混淆，需每次更新后立即比较，全负数时须初始化为nums[0]。
为什么直接遍历所有子数组会超时
暴力解法要枚举 O(n²) 个子数组，对每个再求和，总时间复杂度达 O(n³)；稍作优化（边扩展边累加）能压到 O(n²)，但面对 n > 10⁵ 的输入基本就卡死。Kadane 算法把时间压到 O(n)，核心是「不回溯、只看当前位置结尾的最大子数组和」。
max_ending_here 和 max_so_far 分别管什么
这两个变量分工明确：max_ending_here 表示「以当前元素结尾」的最大子数组和，它要么接上前一个子数组（如果前一个值为正），要么从自己重新开始；max_so_far 则始终记录遍历至今见过的全局最大值。
常见错误是混淆二者用途，比如用 max_so_far 直接更新下一项——这会丢失“必须连续”和“必须以当前结尾”的约束。
- 当
max_ending_here ，说明前面那段已经拖后腿，果断丢弃，重置为当前元素值 - 当
max_ending_here >= 0，加上当前元素可能更大，所以执行max_ending_here += nums[i] -
max_so_far必须在每次更新max_ending_here后立即比较更新，不能延迟
C++ 实现时要注意的边界和类型问题
初始值设错是最常见 bug：若全为负数，max_so_far 初始化为 0 就会返回错误结果（应返回最大负数）。正确做法是初始化为 nums[0]，并从下标 1 开始遍历。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
另外，int 可能溢出——尤其题目没说数值范围时，建议用 long long 存 max_ending_here 和 max_so_far，但注意输入数组仍是 vector<int>&</int>，别误转成 long long 数组增加空间开销。
int maxSubArray(vector<int>& nums) {
if (nums.empty()) return 0;
long long max_ending_here = nums[0];
long long max_so_far = nums[0];
for (int i = 1; i < nums.size(); ++i) {
max_ending_here = max(static_cast<long long>(nums[i]),
max_ending_here + nums[i]);
max_so_far = max(max_so_far, max_ending_here);
}
return static_cast<int>(max_so_far);
}
如何同时返回子数组起止下标
原算法只返回最大和，但实际调试或业务中常需定位位置。只需额外维护两个下标变量：start 和 end，并在 max_ending_here 重置时更新 start，在 max_so_far 更新时同步更新 end。
- 重置
max_ending_here时，令start = i - 更新
max_so_far时，令end = i - 注意：
start不一定等于end，更不是固定为0；它只在“另起炉灶”时才变
这个扩展几乎不增加时间开销，但容易漏掉对 start 的初始化（应设为 0）或误在循环外赋值 end。
