0053. Maximum Subarray
======================
题目信息
--------
:题号: 0053. 最大子数组和
:难度: Medium
:主题: 数组、动态规划、前缀和
:原题: `LeetCode 0053 `_
:重点: 从枚举连续区间,推导到只保留以前一位置结尾的最优非空子数组
题目重述
--------
给定整数数组 ``nums``,选择一个至少包含一个元素的连续子数组,返回该子数组的最大元素和。
子数组必须连续且不能为空。因此数组全部为负数时,答案是最大的单个元素,而不是空子数组的和 ``0``。
约束为 ``1 <= nums.length <= 10^5``、``-10^4 <= nums[i] <= 10^4``。
自建示例
--------
.. code-block:: text
输入:nums = [-4,2,3,-8,5,6,-2]
输出:11
解释:最大和子数组为 [5,6]。跨过 -8 连接前后两段只能得到 8。
.. code-block:: text
输入:nums = [-9,-2,-7]
输出:-2
解释:所有非空连续子数组的和都为负,最优选择是单个元素 -2。
.. code-block:: text
输入:nums = [4,-1,2,1,-7,3]
输出:6
解释:最大和子数组为 [4,-1,2,1]。区间中出现负数并不意味着必须截断。
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
private:
int enumerateSubarrays(const std::vector& nums) {
const int n = static_cast(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& nums) {
const int n = static_cast(nums.size());
std::vector 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& 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& nums) {
int endingHere = nums[0];
int best = nums[0];
for (int index = 1;
index < static_cast(nums.size());
++index) {
endingHere = std::max(
nums[index],
endingHere + nums[index]
);
best = std::max(best, endingHere);
}
return best;
}
public:
int maxSubArray(std::vector& nums) {
return kadane(nums);
}
};
题解
----
区间枚举基线
~~~~~~~~~~~~
连续子数组由左端点 ``left`` 和右端点 ``right`` 唯一确定。固定左端点后,右端点每向右移动一格,只需把新元素加入
累计和:
.. code-block:: text
sum(left, right) = sum(left, right - 1) + nums[right]
``enumerateSubarrays`` 因而能枚举全部候选,同时避免为每个区间重新求和。数组共有 ``O(n²)`` 个非空连续子数组,
所以显式枚举端点仍需平方时间。
继续优化的关键不是更快地计算某个区间和,而是压缩同一右端点对应的全部左端点选择。
右端点状态
~~~~~~~~~~
定义:
.. code-block:: text
ending[i] = 必须以 i 为右端点的非空连续子数组最大和
任何以 ``i`` 结尾的非空连续子数组只有两种来源:
* 从 ``nums[i]`` 重新开始;
* 把 ``nums[i]`` 接到一个以 ``i-1`` 结尾的非空连续子数组后面。
第二类只需保留 ``ending[i-1]``。所有候选都追加同一个 ``nums[i]``,此前和最大的候选追加后仍然最大。因此:
.. code-block:: text
ending[i] = max(nums[i], ending[i-1] + nums[i])
每个非空连续子数组都有唯一右端点。对每个右端点保留该类中的最大和,再在所有 ``ending[i]`` 中取最大值,就覆盖了
全部候选。
右端点不变量
~~~~~~~~~~~~
从左向右处理到下标 ``i`` 后,保持两个状态:
* ``endingHere`` 是所有以 ``i`` 结尾的非空连续子数组中的最大和;
* ``best`` 是前缀 ``nums[0..i]`` 内全部非空连续子数组的最大和。
转移也可以写成:
.. code-block:: text
endingHere = nums[i] + max(0, previousEnding)
若 ``previousEnding`` 为负,连接它只会降低结果,当前最优区间应从 ``nums[i]`` 重新开始;若它为正,连接它会提高
结果。被丢弃的是总贡献为负的整个前缀,不是所有包含负数的区间。``[4,-1,2,1]`` 中的 ``-1`` 仍可保留,因为
此前累计贡献在扩展过程中仍有价值。
随后执行:
.. code-block:: text
best = max(best, endingHere)
这一步同时保留可能早已结束的全局最优区间。循环结束时,``best`` 已比较每个可能右端点,因此就是答案。
初始值必须取 ``nums[0]``。这样 ``endingHere`` 和 ``best`` 从一开始就代表真实的非空区间;若初始化为 ``0``,
全负数组会错误选择不存在的空子数组。
状态演化
~~~~~~~~
对 ``[-4,2,3,-8,5,6,-2]``:
.. list-table::
:header-rows: 1
* - 当前值
- 连接上一段
- 重新开始
- ``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]`` 的和为:
.. code-block:: text
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)`` 额外空间。主入口不修改输入数组。