题目

思路

一句话：从左到右扫描，每一步只决定“接上前面的子数组”还是“从自己重新开始”，同时记录全局最大值。

最直白的做法是枚举所有子数组：枚举起点 i、终点 j，再把中间的元素逐个加起来。这是 O(n³)；用前缀和可以把“求区间和”压到 O(1)，但枚举两端仍然要 O(n²)。本题 n 可到 105，O(n²) 大约是 1010 次操作，明显超时。

关键观察：设 f(i) 表示“必须以 nums[i] 结尾的最大子数组和”。以 i 结尾的子数组只有两类：

• 只含 nums[i] 一个元素，和为 nums[i]；
• 接在某个以 i-1 结尾的子数组后面，前缀最好取 f(i-1)，和为 f(i-1) + nums[i]。

所以有递推式 f(i) = max(nums[i], f(i-1) + nums[i])，最终答案就是所有 f(i) 的最大值。

换个更直观的说法：维护一个当前累计和 total。一旦 total 变成负数，它对后面任何子数组都只会“拖后腿”——宁可把它丢掉，从下一个元素重新开始。这样一遍扫描就够，且只需两个变量，时间 O(n)、空间 O(1)。

解法

用一个变量 cur 存“以当前位置结尾的最大和”，一个变量 best 存全局答案；每到一个新元素，cur 在“重开”和“接上”之间取更大值，再用它更新 best。下表演示自造示例 [3,-5,4,-2,3] 的完整过程：

扫描结束时 best = 5，对应子数组正是 [4,-2,3]。下面 C++ 写递推式，Python 写“累计和变负就清零”的等价版本。

下图把上面的关键过程画成示意图，并逐步演示：

C++

class Solution {
public:
 int maxSubArray(vector<int>& nums) {
 int cur = nums[0];                    // 以当前位置结尾的最大子数组和
 int best = nums[0];                   // 全局最大和（至少取一个元素）  for (int i = 1; i < (int)nums.size(); ++i) {
 // 要么接上前面，要么从 nums[i] 重新开始
 cur = max(nums[i], cur + nums[i]);
 best = max(best, cur);
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。