暴力法需枚举o(n²)子数组并逐个求和，总复杂度o(n³)，预处理前缀和可优化至o(n²)，但面对n>10⁵仍超时；而kadane算法利用连续性实现o(n)线性解法，通过current_sum与global_max两个变量滚动更新，每次仅比较并赋值，兼顾全负数组等边界情况。
为什么不能直接用双重循环暴力求解
暴力法要枚举所有 O(n²) 个子数组，再对每个子数组求和，总时间复杂度是 O(n³)；稍作优化（预处理前缀和）能压到 O(n²)，但面对 n > 10⁵ 的数据就超时。实际工程中，比如处理传感器流式数据或日志滑动窗口，必须用线性解法。
核心矛盾在于：连续子数组的“连续性”提供了状态复用机会——以位置 i 结尾的最大和，只依赖于以 i−1 结尾的结果，无需回看更早的全部组合。
用 std::max 和滚动变量实现 Kadane 算法
Kadane 算法本质是动态规划的极简落地：维护两个变量——current_sum（以当前元素结尾的最大子数组和）、global_max（全局最大和）。每步只做一次比较和一次更新。
关键细节：
-
current_sum = std::max(nums[i], current_sum + nums[i])：决定是“另起炉灶”（只取当前数），还是“接着上一段”（累加） - 初始化
current_sum和global_max必须为nums[0]，不能设为0，否则全负数组会错误返回0 - 整型溢出风险低，但若元素范围极大（如
int64_t且含大正负数），建议用long long中间计算
int maxSubArray(const std::vector<int>& nums) {
int current_sum = nums[0];
int global_max = nums[0];
for (int i = 1; i
<h3>遇到全负数数组时怎么不翻车</h3>
<p>错误写法常把初始值设成 <code>0</code> 或 <code>INT_MIN</code> 后未正确更新，导致返回 <code>0</code>（比如输入 <code>[-5, -2, -8]</code> 期望结果是 <code>-2</code>，而非 <code>0</code>）。</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架"><img
src="https://img.php.cn/upload/skill/000/000/081/178988956499722.jpg" alt="C++ 算法竞赛自动化测试数据生成与校验框架" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="overflowclass">C++ 算法竞赛自动化测试数据生成与校验框架</a>
<p class="overflowclass">根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。</p>
</div>
<a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<p>根本原因：子数组不能为空，必须至少含一个元素。因此初始化必须用首个元素，且每次 <code>std::max</code> 的左操作数必须是当前元素本身（保证“另起炉灶”选项始终有效）。</p>
<p>验证方式：手跑 <code>[-3, -1, -5]</code> ——
第一步：<code>current_sum = max(-1, -3 + (-1)) = -1</code>，<code>global_max = max(-3, -1) = -1</code>；
第二步：<code>current_sum = max(-5, -1 + (-5)) = -5</code>，<code>global_max = max(-1, -5) = -1</code> → 正确。</p>
<h3>想同时返回最大和与子数组下标怎么办</h3>
<p>只需额外记录起始、结束索引。当 <code>current_sum</code> 重置为 <code>nums[i]</code> 时，说明新子数组从 <code>i</code> 开始；当 <code>global_max</code> 更新时，同步更新结束索引 <code>end = i</code>，并根据当前起始推导出 <code>start</code>。</p>
<p>注意点：</p>
<ul>
<li>起始索引只在 <code>current_sum</code> 重置时更新（即 <code>nums[i] > current_sum + nums[i]</code> 成立时）</li>
<li>不要在每次循环都更新 <code>start</code>，否则会丢失原始起点</li>
<li>若需返回子数组内容，用 <code>std::vector<int>(nums.begin() + start, nums.begin() + end + 1)</int></code> 构造即可，避免拷贝整个原数组</li>
</ul>
<p>边界情况如单元素数组、最大和出现在开头或结尾，这套逻辑天然覆盖，不用特判。</p>
实际写的时候最容易漏掉全负数的初始化，或者把 <code>current_sum</code> 更新写成 <code>current_sum += nums[i]</code> 再单独判断，导致无法及时“断开”。Kadane 的精妙正在于把“是否延续”和“更新当前值”压缩进一行 <code>std::max</code>。</int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
