0053. Maximum Subarray

题目信息

题号:
  1. 最大子数组和

难度:

Medium

主题:

数组、动态规划、前缀和

原题:

LeetCode 0053

重点:

从枚举连续区间,推导到只保留以前一位置结尾的最优非空子数组

题目重述

给定整数数组 nums,选择一个至少包含一个元素的连续子数组,返回该子数组的最大元素和。

子数组必须连续且不能为空。因此数组全部为负数时,答案是最大的单个元素,而不是空子数组的和 0。

约束为 1 <= nums.length <= 10^5、-10^4 <= nums[i] <= 10^4。

自建示例

输入:nums = [-4,2,3,-8,5,6,-2]
输出:11
解释:最大和子数组为 [5,6]。跨过 -8 连接前后两段只能得到 8。
输入:nums = [-9,-2,-7]
输出:-2
解释:所有非空连续子数组的和都为负,最优选择是单个元素 -2。
输入:nums = [4,-1,2,1,-7,3]
输出:6
解释:最大和子数组为 [4,-1,2,1]。区间中出现负数并不意味着必须截断。

C++ 实现

#include <algorithm>
#include <climits>
#include <vector>

class Solution {
private:
    int enumerateSubarrays(const std::vector<int>& nums) {
        const int n = static_cast<int>(nums.size());
        int best = INT_MIN;
        for (int left = 0; left < n; ++left) {
            int sum = 0;
            for (int right = left; right < n; ++right) {
                sum += nums[right];
                best = std::max(best, sum);
            }
        }
        return best;
    }

    int dynamicProgramming(const std::vector<int>& nums) {
        const int n = static_cast<int>(nums.size());
        std::vector<int> ending(n);
        ending[0] = nums[0];
        int best = ending[0];

        for (int index = 1; index < n; ++index) {
            ending[index] = std::max(
                nums[index],
                ending[index - 1] + nums[index]
            );
            best = std::max(best, ending[index]);
        }
        return best;
    }

    int prefixMinimum(const std::vector<int>& nums) {
        int prefix = 0;
        int minimumPrefix = 0;
        int best = INT_MIN;

        for (int value : nums) {
            prefix += value;
            best = std::max(best, prefix - minimumPrefix);
            minimumPrefix = std::min(minimumPrefix, prefix);
        }
        return best;
    }

    int kadane(const std::vector<int>& nums) {
        int endingHere = nums[0];
        int best = nums[0];

        for (int index = 1;
             index < static_cast<int>(nums.size());
             ++index) {
            endingHere = std::max(
                nums[index],
                endingHere + nums[index]
            );
            best = std::max(best, endingHere);
        }
        return best;
    }

public:
    int maxSubArray(std::vector<int>& nums) {
        return kadane(nums);
    }
};

题解

区间枚举基线

连续子数组由左端点 left 和右端点 right 唯一确定。固定左端点后,右端点每向右移动一格,只需把新元素加入 累计和:

sum(left, right) = sum(left, right - 1) + nums[right]

enumerateSubarrays 因而能枚举全部候选,同时避免为每个区间重新求和。数组共有 O(n²) 个非空连续子数组, 所以显式枚举端点仍需平方时间。

继续优化的关键不是更快地计算某个区间和,而是压缩同一右端点对应的全部左端点选择。

右端点状态

定义:

ending[i] = 必须以 i 为右端点的非空连续子数组最大和

任何以 i 结尾的非空连续子数组只有两种来源:

  • 从 nums[i] 重新开始;

  • 把 nums[i] 接到一个以 i-1 结尾的非空连续子数组后面。

第二类只需保留 ending[i-1]。所有候选都追加同一个 nums[i],此前和最大的候选追加后仍然最大。因此:

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

每个非空连续子数组都有唯一右端点。对每个右端点保留该类中的最大和,再在所有 ending[i] 中取最大值,就覆盖了 全部候选。

右端点不变量

从左向右处理到下标 i 后,保持两个状态:

  • endingHere 是所有以 i 结尾的非空连续子数组中的最大和;

  • best 是前缀 nums[0..i] 内全部非空连续子数组的最大和。

转移也可以写成:

endingHere = nums[i] + max(0, previousEnding)

若 previousEnding 为负,连接它只会降低结果,当前最优区间应从 nums[i] 重新开始;若它为正,连接它会提高 结果。被丢弃的是总贡献为负的整个前缀,不是所有包含负数的区间。[4,-1,2,1] 中的 -1 仍可保留,因为 此前累计贡献在扩展过程中仍有价值。

随后执行:

best = max(best, endingHere)

这一步同时保留可能早已结束的全局最优区间。循环结束时,best 已比较每个可能右端点,因此就是答案。

初始值必须取 nums[0]。这样 endingHere 和 best 从一开始就代表真实的非空区间;若初始化为 0, 全负数组会错误选择不存在的空子数组。

状态演化

对 [-4,2,3,-8,5,6,-2]:

当前值

连接上一段

重新开始

endingHere

best

-4

—

-4

-4

-4

2

-2

2

2

2

3

5

3

5

5

-8

-3

-8

-3

5

5

2

5

5

5

6

11

6

11

11

-2

9

-2

9

11

在 -8 处,endingHere 必须继续表示以当前位置结尾的最优区间,所以变为 -3;best 仍保留此前的 5。遇到下一个 5 时,重新开始优于连接负贡献前缀。

状态压缩

dynamicProgramming 用数组保存全部 ending[i],清楚展示了状态定义和转移。

由于 ending[i] 只依赖 ending[i-1],可以用 endingHere 覆盖上一状态,得到 kadane。搜索空间没有 变化,额外空间从 O(n) 降为 O(1)。公开入口采用这一实现。

最小前缀视角

定义 prefix[k] 为前 k 个元素之和,则区间 [left,right] 的和为:

prefix[right + 1] - prefix[left]

固定右端点后,当前前缀已经确定。要使区间和最大,只需减去此前出现过的最小前缀。因此 prefixMinimum 在扫描时 维护当前前缀和与此前最小前缀和。

代码先用 prefix - minimumPrefix 更新答案,再把当前 prefix 纳入最小值。这个顺序保证被减去的前缀位于 当前右端点之前,候选区间始终非空。该方法与 Kadane 从不同方向压缩同一批区间候选,时间和空间复杂度相同。

复杂度分析

enumerateSubarrays 枚举 O(n²) 个区间,时间 O(n²)、额外空间 O(1)。

dynamicProgramming、prefixMinimum 和 kadane 都只扫描一次,时间 O(n)。DP 数组使用 O(n) 额外空间,后两种方法使用 O(1) 额外空间。主入口不修改输入数组。