kadane算法中max_ending_here重置为当前元素而非0,是因为子数组必须非空且连续;若设为0,则隐含“可不选元素”,违反题意——当全为负数时将错误返回0而非最大负数。

为什么 max_ending_here 重置时必须设为当前元素而非 0
因为子序和必须连续,且至少包含一个元素。当 max_ending_here + nums[i] ,说明前面的累加段已拖累当前值,最优策略是“从 <code>nums[i] 重新开始”。此时起始索引不能继承旧起点,而要更新为 i。若设为 0,会丢失负数数组(如 [-5, -2])中最大单元素的合法性。
如何在更新 max_so_far 时同步记录起止索引
只靠一个变量无法回溯起点,必须维护三个状态变量:max_ending_here、start_temp(当前段临时起点)、end_idx(当前段终点)。每次更新全局最大值时,把 start_temp 和当前 i 赋给最终的 left 和 right。
关键逻辑如下:
int max_so_far = nums[0];
int max_ending_here = nums[0];
int start_temp = 0, left = 0, right = 0;
for (int i = 1; i max_so_far) {
max_so_far = max_ending_here;
left = start_temp;
right = i;
}
}
nums[i] 为负但 max_ending_here 仍为正时要不要更新 start_temp
不更新。只要 max_ending_here >= 0,继续累加就有意义——即使加入负数,也可能为后续更大正数保留连接性(例如 [4, -1, 5]:4→3→8,起点始终是 0)。只有当 max_ending_here 变成负数,才说明当前段已无价值,必须在下一位置重置起点。
组合式C++代码评审方案,融合静态分析、AI推理、多轮迭代评审和C++专项检查,适用于PR审查、增量代码审查、全项目评审和代码质量评分,触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 错误做法:每次
nums[i] 就重置 <code>start_temp - 正确依据:转移条件只看
max_ending_here的符号,不是看nums[i] - 边界注意:全负数组中,
start_temp和left最终指向最大那个负数的索引,不是 0
为什么不能用 std::max 简化判断逻辑
因为 std::max(a + b, b) 看似等价于 a ,但会掩盖起始索引更新时机。前者只返回值,无法触发 <code>start_temp = i 这一副作用;后者天然将“是否重置起点”与“是否更新最大值”解耦,语义清晰且可审计。
尤其当需要返回子数组本身(而不仅是和)时,索引更新必须显式、及时、与值计算严格同步——隐式 std::max 容易漏掉这一层控制流。
实际编码中,宁可用两行 if,也不要为省一行代码牺牲状态可追踪性。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!










