跳到主要内容

LeetCode 53. 最大子数组和

本节目标

维护必须以当前位置结尾的最大连续和，避免把不连续正数相加。

这是动态规划基础与线性状态中“连续区间必须收尾”的母题。

题意与约束​

求非空连续子数组的最大和；元素可为负数，答案不能默认为零。

第一反应与重复子问题​

处理当前位置时，只需判断是从它重新开段，还是接在前一个连续段之后；“以前一位结尾”的答案会重复使用。

状态定义与转移推导​

令 dp[i] 为必须以 i 结尾的最大和，dp[i]=max(nums[i], dp[i-1]+nums[i])。全局答案是所有 dp[i] 的最大值。

正确性依据​

任何以 i 结尾的连续段，前面要么为空，要么恰是以 i-1 结尾的连续段；取两者较优即穷尽所有可能。

样例执行过程​

在 [-2,1,-3,4,-1,2,1,-5,4] 中，结尾状态到 4,-1,2,1 时形成和为 6 的段。

代码实现​

C++17
#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int endingHere = nums[0], best = nums[0];
        for (int index = 1; index < static_cast<int>(nums.size()); index++) {
            endingHere = max(nums[index], endingHere + nums[index]);
            best = max(best, endingHere);
        }
        return best;
    }
};

复杂度分析​

一次扫描，时间 O(n)，滚动状态空间 O(1)。

边界与易错点​

  • 全负数组必须返回其中最大的元素。
  • 状态必须规定“以当前位置结尾”，否则会错误拼接不连续元素。

模式迁移​

最大乘积子数组在同一框架上额外维护最小值；环形数组版本则需分开处理首尾连接。