环形数组最大子数组和等于max(普通最大子数组和, 总和−最小子数组和),但需特判全负数情况,此时直接返回普通最大值。

为什么总和减最小子数组和能算环形最大和
环形数组的最大子数组和,要么是普通非环形最大和(不跨尾到头),要么是总和减去中间一段“最负”的连续子数组——也就是总和减最小子数组和。关键在于:跨环的最优解 = 所有元素加起来,再把中间拖后腿最狠的一段切掉。
但要注意一个边界:如果数组全为负数,max_subarray_sum 就是最大的那个负数,而 total_sum - min_subarray_sum 会等于 0(因为 min_subarray_sum == total_sum),结果错误。所以必须单独判断是否所有数都 ≤ 0。
怎么写最小子数组和(Kadane 变体)
和求最大子数组和的 Kadane 算法对称:把比较方向反过来,初始化用 INT_MAX,更新时取 min(current_sum + num, num)。
组合式C++代码评审方案,融合静态分析、AI推理、多轮迭代评审和C++专项检查,适用于PR审查、增量代码审查、全项目评审和代码质量评分,触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 不能直接对原数组取负再跑一遍最大和——浮点或溢出风险高,逻辑也绕
-
min_so_far初始值必须是INT_MAX,不是 0;否则第一个负数就卡住 - 要允许子数组长度为 1,所以每次都要做
min_so_far = min(min_so_far, current_sum),不能只在更新current_sum后才比
int min_subarray_sum = INT_MAX;
int current_min = 0;
for (int x : nums) {
current_min = min(x, current_min + x);
min_subarray_sum = min(min_subarray_sum, current_min);
}
环形情况要排除全负数陷阱
当 max_subarray_sum ,说明整个数组没有正数,此时环形解不可能靠“挖掉一段”变大——因为挖掉任何一段只会让和更小(总和已经是负的,再减一个负数等于加正数?不对:注意 <code>total - min 中 min 是负数,所以 total - min = 负 - 负 = 更负或略大,但最大也就等于 <code>max_subarray_sum)。实际此时唯一合法解就是 max_subarray_sum。
- 判断条件用
max_subarray_sum ,而不是 <code>min_subarray_sum == total_sum,更直接可靠 - 不需要特判空数组,题目通常保证
nums.size() > 0 - 不要在计算
total_sum时用accumulate却忘了long long——若nums元素范围大,int总和可能溢出
完整逻辑里总和和最小子数组和的调用时机
必须先算出 max_subarray_sum 和 min_subarray_sum,再算 total_sum;或者把 total_sum 放在最前面单独扫一次。不能边算 max/min 边累加 total 再混用——容易因初始化顺序导致 min 比 total 少算一个数。
- 推荐做法:第一遍循环算
total_sum和max_subarray_sum;第二遍算min_subarray_sum(或一遍完成三个变量,但需小心初始化) - 如果一遍完成,
current_max和current_min必须各自独立初始化,且total_sum累加放在最外层 - 返回时写成:
max(max_subarray_sum, total_sum - min_subarray_sum),但前面加一层if (max_subarray_sum
真正容易漏的是全负数判断——很多人写了 total - min 却没兜底,一遇到 [-3,-2,-1] 就返回 0,错得无声无息。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!










