因为暴力枚举所有子数组时间复杂度为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 <h3>想同时返回子数组区间？改两行就行</h3>
<p>原算法只关心最大和，但实际调试或业务中常需知道起止下标。只需额外记录 <code>start</code>、<code>end</code> 和临时起点 <code>temp_start</code>：</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
</div>
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<ul>
<li>当 <code>nums[i] > max_ending_here + nums[i]</code> 成立，说明要重开子数组，此时 <code>temp_start = i</code>
</li>
<li>当 <code>max_so_far</code> 被更新，就同步更新 <code>start = temp_start</code> 和 <code>end = i</code>
</li>
<li>注意：<code>start</code> 和 <code>end</code> 是闭区间，返回时可直接用 <code>vector<int>(nums.begin()+start, nums.begin()+end+1)</int></code>
</li>
</ul>
<h3>遇到浮点数或大整数怎么办</h3>
<p><code>Kadane</code> 本身不限制数值类型，但要注意溢出和精度：</p>
<ul>
<li>若用 <code>double</code>，比较操作（如 <code>max(a,b)</code>）仍安全，但累加可能丢失精度；建议改用 <code>long double</code> 或定点运算</li>
<li>若元素是 <code>long long</code> 且范围接近 <code>LLONG_MAX</code>，加法可能溢出，需在相加前检查：<code>if (max_ending_here > 0 && nums[i] > LLONG_MAX - max_ending_here)</code> 则强制重开</li>
<li>STL 的 <code>max</code> 对自定义类型需重载 <code>，别直接套用 <code>std::max</code> 而不确认比较逻辑</code>
</li>
</ul>
<p>最易被忽略的是：算法假设数组非空。传入空 <code>vector</code> 时，第一行 <code>nums[0]</code> 会越界——调用前务必加 <code>if (nums.empty()) throw runtime_error("empty array")</code> 或约定返回 0 / 特殊值。</p></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
