0152. Maximum Product Subarray
==============================
题目信息
--------
:题号: 0152. 乘积最大子数组
:难度: Medium
:主题: 数组、动态规划、符号翻转、滚动状态
:原题: `LeetCode 0152 `_
:重点: 为每个右端点同时保留最大积与最小积,让负数乘法能够交换两类候选,并允许从当前值重新开始
题目重述
--------
给定非空整数数组 ``nums``,选择一个连续且非空的子数组,返回其中所有元素乘积的最大值。不能跳过中间
元素,也不能用空子数组贡献乘积一。题目保证相关乘积和答案可由 32 位有符号整数表示。
自建示例
--------
* ``[-2, 5, -3]``:整个数组乘积为 ``30``,两个负数使积重新为正;
* ``[-1, -2, -3, 0, 4]``:``[-2, -3]`` 的乘积 ``6`` 最大,零把左右候选区间隔开;
* ``[-5]``:必须选择非空子数组,答案是 ``-5``,不能返回初始化单位元 ``1``;
* ``[0, -2, 0]``:单独的零优于负数,答案为 ``0``。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
int enumerateEverySubarray(const std::vector& nums) {
int answer = nums[0];
for (int left = 0;
left < static_cast(nums.size());
++left) {
int product = 1;
for (int right = left;
right < static_cast(nums.size());
++right) {
product *= nums[right];
answer = std::max(answer, product);
}
}
return answer;
}
int trackBothEndingExtremes(const std::vector& nums) {
int maximumEndingHere = nums[0];
int minimumEndingHere = nums[0];
int answer = nums[0];
for (int index = 1;
index < static_cast(nums.size());
++index) {
const int value = nums[index];
const int previousMaximum = maximumEndingHere;
const int previousMinimum = minimumEndingHere;
maximumEndingHere = std::max({
value,
previousMaximum * value,
previousMinimum * value
});
minimumEndingHere = std::min({
value,
previousMaximum * value,
previousMinimum * value
});
answer = std::max(answer, maximumEndingHere);
}
return answer;
}
public:
int maxProduct(std::vector& nums) {
return trackBothEndingExtremes(nums);
}
};
题解
----
原始空间:每个左右端点都是候选
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
最直接的 ``enumerateEverySubarray`` 固定左端点,向右逐个乘入元素;这样比每次从头计算乘积少了重复乘法,
但仍有 ``O(n^2)`` 个连续区间。许多区间共享相同右端点和前缀,只是从不同位置开始,算法没有压缩它们对
未来的影响。
若从左向右扫描,新子数组要么只含当前元素,要么由某个“以上一位置结尾”的子数组追加当前值。连续性因此
让状态可以按右端点递推,不需要保留任意更早的结束位置。
为什么最大和问题的一项状态不够
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
若是最大子数组和,较小前缀加上同一个值仍然较小,只保留最大值即可。乘法的顺序关系会被负数反转:一个
很小的负积乘负数,可能成为最大的正积;原来的最大正积乘负数则可能成为新的最小积。因此只保存
``maximumEndingHere`` 会永久丢掉未来翻盘所需的负候选。
对每个位置必须同时保存:
* ``maximumEndingHere``:所有以当前位置结尾的非空子数组中的最大乘积;
* ``minimumEndingHere``:同一集合中的最小乘积。
这两个极值足够。追加当前值是对旧乘积统一乘一个常数:常数为正时顺序不变,旧最大/最小仍产生新两端;
常数为负时顺序反转,旧最小/最大交换角色;常数为零时所有延长候选都归零。中间值不可能越过两端成为新
极值。
三类候选怎样表达继续与重启
~~~~~~~~~~~~~~~~~~~~~~~~~~
以当前位置结尾的子数组只有三种可能来源:
.. code-block:: text
value 从当前位置重新开始
previousMaximum * value 延长旧最大积子数组
previousMinimum * value 延长旧最小积子数组
最大状态取三者最大,最小状态取三者最小。单独选择 ``value`` 很关键:此前前缀可能为零或会让结果更差,
当前元素必须能成为新子数组起点。它也让零自然完成分隔,无需显式清空状态;读到零时三候选都包含零或由零
比较,后一个非零位置又能通过自己的 ``value`` 重启。
状态更新为何要先保存旧值
~~~~~~~~~~~~~~~~~~~~~~~~
新最大值和新最小值都依赖同一轮的旧最大、旧最小。若先覆盖 ``maximumEndingHere``,再用它计算最小值,
第二个状态会错误使用“已经乘过当前元素”的结果,相当于把当前值重复乘入。代码用
``previousMaximum``、``previousMinimum`` 拍下同一时刻的快照,再并行生成两端。
具体走读负数翻转
~~~~~~~~~~~~~~~~
对 ``[-2, 5, -3]``:
.. list-table::
:header-rows: 1
* - 当前值
- 三个候选
- 新最大 / 新最小
- 全局答案
* - ``-2``
- 初始单元素
- ``-2 / -2``
- ``-2``
* - ``5``
- ``5, -10, -10``
- ``5 / -10``
- ``5``
* - ``-3``
- ``-3, -15, 30``
- ``30 / -15``
- ``30``
第三步的 ``30`` 正是旧最小 ``-10`` 乘负数得到;若上一轮只保留最大 ``5``,结果最多看到 ``-3`` 与
``-15``,会漏掉正确答案。
全局答案与结尾状态为何分开
~~~~~~~~~~~~~~~~~~~~~~~~~~
两个滚动状态只描述“必须以当前位置结尾”的区间,用于向下一位置传播;最优子数组可能早已在前面结束,
所以还要用 ``answer`` 保存所有右端点最大状态的最大值。三者都以 ``nums[0]`` 初始化,保证单元素、全负数
输入仍选择真实非空区间,而不是错误的零或一。
主解选择与复杂度
~~~~~~~~~~~~~~~~
公开入口采用双极值滚动 DP。每个元素只计算常数个候选,时间 ``O(n)``;只保存旧、新极值和全局答案,
额外空间 ``O(1)``。区间枚举时间 ``O(n^2)``、空间 ``O(1)``,保留它作为原始候选空间;主解利用符号对
顺序的有限三种作用,将所有同右端点区间压缩为两个极值。