跳转至

53 最大子数组和

前缀和

看到连续子数组的和会想到使用前缀和

但是不同的地方在于,我们需要保证连续子数组的和最大,也就是说假设区间[j,i]的和最大,sum[i] - sum[j - 1]最大

当我们遍历到i时,sum[i]可以i通过sum[i] = sum[i - 1] + num[i]获得,因此我们可以将其看作是定值

那么想要和最大,就需要sum[j - 1]最小,方法也很简单,只需要遍历的时候维护一个最小值前缀和preMin即可

值得注意的是,计算顺序不能乱,必须是:

  1. 计算前缀和pre
  2. 计算连续子数组和ans
  3. 更新最小前缀和

如果Step2 和 Step3顺序交换,那么会出现sum[i] - sum[j]的情况,对应的区间是空的,而本题要求子数组至少含有一个元素

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0;
        // preMin初始化需要为0
        // 保证第一个元素的ans为pre
        int preMin = 0;
        // ans可能为负数,因此需要定义为最小值
        int ans = INT_MIN;
        for(int num : nums){
            // 更新前缀和
            pre += num;
            ans = max(ans, pre - preMin);
            preMin = min(preMin, pre);
        }
        return ans;
    }
};
  • 时间复杂度:O(n),其中 n 为 nums 的长度。
  • 空间复杂度:O(1)。仅用到若干额外变量

动态规划

思路也很简单:

  • 因为连续子数组的和是否取当前元素,取决于本元素前的元素的连续子数组的和,这符合动态规划
  • dp[i]表示nums[i]结尾的子数组的和的最大值
  • 递推公式dp[i] = max(dp[i - 1], 0) + nums[i]
    • 如果前一个元素为负数,那么加上这个元素之后,连续子数组的和只会更小
    • 只有前一个元素为非负数,加上这个元素之后,连续子数组的和才会更大
  • 初始化:dp[0]表示nums[0]结尾的子数组的和的最大值,也就是nums[0]
  • 遍历顺序:从左到右
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];
        int ans = dp[0];
        for(int i = 1; i < n; i++){
            dp[i] = max(dp[i - 1], 0) + nums[i];
            ans = max(ans,dp[i]);
        }
        return ans;
    }
};