C++如何求一个数组的连续子数组最大和-C++-PHP中文网

不能直接用两层循环暴力求解，因为时间复杂度o(n²)在n=10⁵时会超时，且易错判全负数等边界情况；正确解法是动态规划，用cur_sum和max_sum两个变量滚动更新，核心是cur_sum = max(nums[i], cur_sum + nums[i])。

c++如何求一个数组的连续子数组最大和

为什么不能直接用两层循环暴力求解

暴力法时间复杂度是 O(n²)，对长度 10⁵ 的数组会超时；而且容易忽略边界情况，比如全负数时返回 0 就错了——实际应返回最大那个负数。

真正可靠的解法是动态规划，核心就一句话：dp[i] 表示以第 i 个元素结尾的最大连续子数组和。状态转移只看前一个结果要不要“接上”：

如果 dp[i-1] > 0，就接： dp[i] = dp[i-1] + nums[i]
否则从头来： dp[i] = nums[i]

实际写的时候不需要开数组，用两个变量滚动更新就行。

怎么用 `std::max` 和单变量实现（推荐写法）

这是最简洁、不易出错的 C++ 实现，空间 O(1)，时间 O(n)：

int maxSubArray(vector<int>& nums) {
    int cur_sum = nums[0];
    int max_sum = nums[0];
    for (int i = 1; i 
<p>注意两点：</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>
<ul>
<li>
<code>cur_sum</code> 始终表示“以当前元素结尾”的最优解，不是全局最大值</li>
<li>初始化必须用 <code>nums[0]</code>，不能设成 0，否则全负数时会错</li>
</ul>
<h3>遇到 <code>INT_MIN</code> 或大数溢出怎么办</h3>
<p>如果数组里有极大正负数，<code>int</code> 可能溢出。但题目没说数据范围时，先按 <code>int</code> 写；若明确可能越界，改用 <code>long long</code>：</p>
<pre class="brush:php;toolbar:false;">long long cur_sum = nums[0];
long long max_sum = nums[0];

别用 LLONG_MIN 初始化——那会导致第一次 max() 比较失效；仍该用首元素初始化。

另外，C++17 起支持 std::reduce 并行版本，但不适用于这个 DP 场景，强行套用反而逻辑错误。