Sign in Subscribe
算法

最大子数组和

loser

• 8 min read
Share

给你一个整数数组 nums，请你找出一个具有最大和的连续子数组，子数组最少包含一个元素，返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

进阶： 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解法一（动态规划）：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int dp = nums[0];
        int ans = nums[0];

        for (int i = 1; i < nums.size(); i++)
        {
            dp = max(nums[i], dp + nums[i]);
            ans = max(ans, dp);
        }

        return ans;
    }
};

解法二（分治法）：

class Solution {
public:
    struct Status {
        int lSum;
        int rSum;
        int mSum;
        int iSum;
    };

    Status pushUp(Status left, Status right) {
        int iSum = left.iSum + right.iSum;
        int lSum = max(left.lSum, left.iSum + right.lSum);
        int rSum = max(right.rSum, right.iSum + left.rSum);
        int mSum = max(max(left.mSum, right.mSum), left.rSum + right.lSum);

        return {lSum, rSum, mSum, iSum};
    }

    Status get(vector<int>& nums, int l, int r) {
        if (l == r)
        {
            return {nums[l], nums[l], nums[l], nums[l]};
        }

        int mid = l + (r - l) / 2;
        Status left = get(nums, l, mid);
        Status right = get(nums, mid + 1, r);

        return pushUp(left, right);
    }

    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};

核心思想

这题要求的是连续子数组的最大和。

因为子数组必须连续，所以当我们遍历到某个位置 i 时，可以思考一个更具体的问题：

以 nums[i] 作为结尾的最大子数组和是多少？

如果我们能知道每个位置作为结尾时的最大子数组和，那么最终答案就是这些值中的最大值。

这就是动态规划的核心。

动态规划状态定义

定义：

dp[i] 表示以 nums[i] 结尾的连续子数组的最大和。

注意，这里必须强调“以 nums[i] 结尾”。

因为如果不固定结尾位置，状态之间就很难递推。

例如：

nums = [-2, 1, -3, 4]

当我们计算到 4 时，只需要知道“以前一个位置 -3 结尾的最大子数组和”是否值得继续接上 4。

而不需要关心所有历史子数组的具体形状。

状态转移公式

考虑 dp[i]。

一个以 nums[i] 结尾的最大子数组，只有两种选择：

  1. 只选 nums[i] 自己，从当前位置重新开始。
  2. 接在前一个位置的最大子数组后面，也就是 dp[i - 1] + nums[i]。

所以：

dp[i] = max(nums[i], dp[i - 1] + nums[i])

这个公式也可以理解成：

  • 如果 dp[i - 1] 是负数，那么接上它只会让当前和变小，不如从 nums[i] 重新开始。
  • 如果 dp[i - 1] 是正数，那么接上它会让当前和变大，应该继续延伸。

最终答案是：

ans = max(dp[0], dp[1], ..., dp[n - 1])

代码中没有使用完整数组，而是用一个变量 dp 保存上一个状态：

dp = max(nums[i], dp + nums[i]);
ans = max(ans, dp);

为什么不能把答案初始化为 0

这题子数组最少包含一个元素，而且数组中可能全是负数。

例如：

nums = [-3, -2, -5]

最大子数组和应该是 -2。

如果把答案初始化为 0，就会错误返回 0，但空数组并不是合法子数组。

所以：

int dp = nums[0];
int ans = nums[0];

必须从第一个元素开始初始化。

正确性证明

我们证明动态规划算法返回的 ans 是所有连续子数组中的最大和。

结论 1：dp[i] 正确表示以 nums[i] 结尾的最大子数组和

用数学归纳法证明。

当 i = 0 时，以 nums[0] 结尾的子数组只有一个：

[nums[0]]

所以：

dp[0] = nums[0]

正确。

假设 dp[i - 1] 已经正确表示以 nums[i - 1] 结尾的最大子数组和。

现在考虑 dp[i]。

任何以 nums[i] 结尾的连续子数组，要么：

  • 只包含 nums[i]
  • 在某个以 nums[i - 1] 结尾的连续子数组后面接上 nums[i]

如果选择第二种情况，为了让总和最大，前半部分一定要选择以 nums[i - 1] 结尾的最大子数组，也就是 dp[i - 1]。

所以：

dp[i] = max(nums[i], dp[i - 1] + nums[i])

因此 dp[i] 正确。

由归纳法可知，所有 dp[i] 都正确。

结论 2：最大子数组和一定会被 ans 统计到

任意一个连续子数组都有一个确定的右端点。

假设全局最大子数组的右端点是 r。

那么这个子数组一定是“以 nums[r] 结尾的某个连续子数组”。

而 dp[r] 表示所有以 nums[r] 结尾的连续子数组中的最大和。

所以全局最大子数组和一定小于等于 dp[r]，并且会在更新：

ans = max(ans, dp);

时被统计到。

因此最终 ans 就是全局最大子数组和。

分治法核心思想

进阶要求中提到可以用分治法。

分治法的思路是：把数组分成左右两部分，那么最大子数组只可能有三种情况：

  1. 完全在左半部分。
  2. 完全在右半部分。
  3. 跨过中点，同时包含左半部分的后缀和右半部分的前缀。

所以只要每个区间能提供足够的信息，就可以把左右两个区间合并成一个更大的区间。

对于一个区间，我们维护四个值：

  • iSum：整个区间的总和。
  • lSum：必须从区间左端点开始的最大子数组和。
  • rSum：必须以区间右端点结束的最大子数组和。
  • mSum：区间内部的最大子数组和。

最终整个数组的 mSum 就是答案。

分治公式推导

设左区间状态是 left，右区间状态是 right。

合并后的总和：

iSum = left.iSum + right.iSum

合并后的 lSum，也就是必须从整个区间左端点开始的最大子数组和。

它有两种情况：

  1. 只在左区间里，值是 left.lSum
  2. 包含整个左区间，再接上右区间的最大前缀，值是 left.iSum + right.lSum

所以：

lSum = max(left.lSum, left.iSum + right.lSum)

合并后的 rSum 同理：

  1. 只在右区间里，值是 right.rSum
  2. 包含整个右区间，再接上左区间的最大后缀，值是 right.iSum + left.rSum

所以：

rSum = max(right.rSum, right.iSum + left.rSum)

合并后的 mSum，也就是整个区间内部的最大子数组和，有三种情况：

  1. 最大子数组完全在左区间，值是 left.mSum
  2. 最大子数组完全在右区间，值是 right.mSum
  3. 最大子数组跨过中点，值是 left.rSum + right.lSum

所以：

mSum = max(left.mSum, right.mSum, left.rSum + right.lSum)

代码中写成：

int mSum = max(max(left.mSum, right.mSum), left.rSum + right.lSum);

分治法正确性证明

对于任意区间 [l, r]，我们证明它返回的四个值都是正确的。

归纳基

当 l == r 时，区间只有一个元素 nums[l]。

此时：

  • 整个区间和是 nums[l]
  • 从左端点开始的最大子数组和是 nums[l]
  • 以右端点结束的最大子数组和是 nums[l]
  • 区间最大子数组和也是 nums[l]

所以四个值都等于 nums[l]，正确。

归纳假设

假设左右两个子区间返回的四个值都正确。

归纳推导

合并区间时：

  • iSum 只能是左右总和相加。
  • lSum 要么只取左区间前缀，要么取完整左区间加右区间前缀。
  • rSum 要么只取右区间后缀，要么取左区间后缀加完整右区间。
  • mSum 要么在左边，要么在右边，要么跨越中点。

这四种计算都覆盖了所有可能情况，并且每种情况都取了最大值。

所以合并后的四个值正确。

由归纳法可知，整个数组区间的 mSum 正确，也就是最大子数组和。

举例理解

以：

nums = [-2,1,-3,4,-1,2,1,-5,4]

动态规划过程中的几个关键位置：

  • 到 1 时，前面的 -2 是负贡献，所以从 1 重新开始，当前最大结尾和是 1
  • 到 4 时，前面的最大结尾和已经被负数拖累，不如从 4 重新开始
  • 到 -1 时，接在 4 后面得到 3
  • 到 2 时，继续接上得到 5
  • 到 1 时，继续接上得到 6

所以最大和是：

4 + (-1) + 2 + 1 = 6

复杂度分析

动态规划

  • 遍历数组一次
  • 时间复杂度：O(n)
  • 只使用常数个变量
  • 空间复杂度：O(1)

分治法

每一层递归都会合并所有区间，总工作量是 O(n)。

递归层数是 O(log n)。

但每个元素只会在每一层参与一次合并，从递归式来看：

T(n) = 2T(n / 2) + O(1)

所以时间复杂度是：

O(n)

递归栈深度是 O(log n)，所以空间复杂度是：

O(log n)