乘积最大子数组

给你一个整数数组 nums。

请你找出数组中乘积最大的非空连续子数组，并返回该子数组所对应的乘积。

该子数组中至少包含一个数字。

测试用例的答案是一个 32 位整数。

请注意，一个只包含一个元素的数组的乘积就是这个元素的值。

示例 1：

输入：nums = [2,3,-2,4]
输出：6
解释：子数组 [2,3] 有最大乘积 6。

示例 2：

输入：nums = [-2,0,-1]
输出：0
解释：结果不能为 2，因为 [-2,-1] 不是子数组。

提示：

• 1 <= nums.length <= 2 * 10^4
• -10 <= nums[i] <= 10
• nums 的任何子数组的乘积都保证是一个 32 位整数

解法一（动态规划数组）：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();

        vector<int> dpMax(n, 0);
        vector<int> dpMin(n, 0);

        dpMax[0] = nums[0];
        dpMin[0] = nums[0];

        int ans = nums[0];

        for (int i = 1; i < n; i++)
        {
            int x = nums[i];

            dpMax[i] = max(x, max(dpMax[i - 1] * x, dpMin[i - 1] * x));
            dpMin[i] = min(x, min(dpMax[i - 1] * x, dpMin[i - 1] * x));

            ans = max(ans, dpMax[i]);
        }

        return ans;
    }
};

解法二（滚动变量优化）：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxProd = nums[0];
        int minProd = nums[0];
        int ans = nums[0];

        for (int i = 1; i < nums.size(); i++)
        {
            int x = nums[i];

            int oldMax = maxProd;
            int oldMin = minProd;

            maxProd = max(x, max(oldMax * x, oldMin * x));
            minProd = min(x, min(oldMax * x, oldMin * x));

            ans = max(ans, maxProd);
        }

        return ans;
    }
};

核心思想

这题和“最大子数组和”很像，都是连续子数组问题。

但是乘积比加法多了一个麻烦点：

负数会把当前最大乘积变成最小乘积，也会把当前最小乘积变成最大乘积。

例如：

nums = [2, 3, -2]

在看到 -2 之前，最大乘积是 6。

但乘上 -2 以后，6 * -2 = -12，反而变成了很小的数。

再比如：

nums = [-2, 3, -4]

当走到 -4 时，前面最小乘积 -6 乘上 -4 会变成 24。

所以只维护“最大乘积”是不够的。

必须同时维护：

• 以当前位置结尾的最大乘积
• 以当前位置结尾的最小乘积

状态定义

定义：

dpMax[i] 表示以 nums[i] 结尾的连续子数组的最大乘积。

dpMin[i] 表示以 nums[i] 结尾的连续子数组的最小乘积。

题目要求的是所有连续子数组中的最大乘积。

所以最终答案是：

max(dpMax[i])

其中 0 <= i < n。

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

因为连续子数组如果要以 nums[i] 结尾，那么它只有两种来源：

• 从 nums[i] 自己重新开始
• 接在以 nums[i - 1] 结尾的连续子数组后面

递推公式推导

设当前数字是：

x = nums[i]

如果一个最大乘积子数组以 nums[i] 结尾，那么它可能来自三种情况。

1. 只选择当前数字

从当前位置重新开始：

x

2. 接在之前最大乘积后面

如果前面的最大乘积继续乘上当前数字：

dpMax[i - 1] * x

当 x 是正数时，这通常可能成为新的最大值。

3. 接在之前最小乘积后面

如果前面的最小乘积继续乘上当前数字：

dpMin[i - 1] * x

当 x 是负数时，最小乘积乘以负数，可能反而变成新的最大值。

所以：

dpMax[i] = max(x, dpMax[i - 1] * x, dpMin[i - 1] * x)

同理，最小乘积也来自这三种情况：

dpMin[i] = min(x, dpMax[i - 1] * x, dpMin[i - 1] * x)

代码中写成：

dpMax[i] = max(x, max(dpMax[i - 1] * x, dpMin[i - 1] * x));
dpMin[i] = min(x, min(dpMax[i - 1] * x, dpMin[i - 1] * x));

为什么必须维护最小乘积

最大和问题只需要维护最大值，因为加上一个数不会改变大小关系。

但是乘积不同。

如果当前数字是负数，大小关系会反过来：

-10 * -2 = 20
5 * -2 = -10

原来的最小值 -10 乘上负数后，变成了更大的正数。

原来的最大值 5 乘上负数后，变成了更小的负数。

所以在乘积问题中，当前最大值可能来自之前的最小值。

这也是本题和“最大子数组和”的最大区别。

边界情况

数组长度至少为 1。

由于子数组必须非空，所以答案不能初始化为 0。

例如：

nums = [-2]

答案应该是 -2。

因此需要初始化为：

dpMax[0] = nums[0];
dpMin[0] = nums[0];
ans = nums[0];

如果当前数字是 0，递推公式也能自然处理。

因为：

x = 0

时：

dpMax[i] = max(0, 0, 0) = 0
dpMin[i] = min(0, 0, 0) = 0

这相当于把前面的乘积链条断开。

后面的子数组可以从 0 后面重新开始。

解法二：滚动变量优化

观察递推公式：

dpMax[i] 只依赖 dpMax[i - 1] 和 dpMin[i - 1]
dpMin[i] 只依赖 dpMax[i - 1] 和 dpMin[i - 1]

所以不需要保存完整的 dpMax 和 dpMin 数组。

只需要两个变量：

• maxProd：以当前位置结尾的最大乘积
• minProd：以当前位置结尾的最小乘积

更新时要先保存旧值：

int oldMax = maxProd;
int oldMin = minProd;

因为新的 maxProd 和新的 minProd 都要同时依赖上一轮的两个值。

如果先更新 maxProd，再用新的 maxProd 去算 minProd，状态就会混乱。

所以滚动变量版本写成：

maxProd = max(x, max(oldMax * x, oldMin * x));
minProd = min(x, min(oldMax * x, oldMin * x));

这样空间复杂度就从 O(n) 优化到了 O(1)。

正确性证明

我们证明：算法返回的 ans 是数组中所有非空连续子数组的最大乘积。

结论 1：dpMax[i] 正确表示以 nums[i] 结尾的连续子数组最大乘积

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

[nums[0]]

所以：

dpMax[0] = nums[0]

正确。

当 i > 0 时，任意一个以 nums[i] 结尾的连续子数组只有两种情况：

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

如果接在前面子数组后面，那么由于乘以负数可能改变大小关系，最大乘积只可能来自：

• 上一位置的最大乘积
• 上一位置的最小乘积

因此取：

max(nums[i], dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i])

就覆盖了所有可能，并且不会加入不连续的子数组。

所以 dpMax[i] 正确。

结论 2：dpMin[i] 正确表示以 nums[i] 结尾的连续子数组最小乘积

同理，以 nums[i] 结尾的连续子数组也只能：

• 从 nums[i] 重新开始
• 接在以 nums[i - 1] 结尾的连续子数组后面

最小乘积也只可能来自：

nums[i]

dpMax[i - 1] * nums[i]

dpMin[i - 1] * nums[i]

取三者最小值，就能得到以 nums[i] 结尾的最小乘积。

所以 dpMin[i] 正确。

结论 3：ans 正确记录了所有位置结尾的最大乘积

任意非空连续子数组一定有一个结束位置。

如果它结束在位置 i，那么它的乘积一定不会超过 dpMax[i]。

算法每计算完一个位置，就执行：

ans = max(ans, dpMax[i]);

所以遍历结束后，ans 就是所有 dpMax[i] 中的最大值。

也就是所有非空连续子数组的最大乘积。

结论 4：滚动变量版本和数组版本等价

滚动变量版本中的 maxProd 对应当前的 dpMax[i]。

minProd 对应当前的 dpMin[i]。

每次更新前保存：

oldMax = maxProd;
oldMin = minProd;

它们分别对应上一轮的 dpMax[i - 1] 和 dpMin[i - 1]。

因此滚动变量版本使用的递推公式和数组版本完全一致。

得出结论

由结论 1 和结论 2 可知，每个位置的最大、最小乘积状态都计算正确。

由结论 3 可知，ans 是所有连续子数组乘积中的最大值。

由结论 4 可知，滚动变量优化不会改变算法结果。

因此算法正确。

举例理解

以：

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

为例。

最终答案是 6，对应子数组：

[2,3]

再看：

nums = [-2,0,-1]

因为子数组必须连续，[-2,-1] 不是连续子数组。

遇到 0 时，乘积链条被断开。

最终最大乘积是：

0

复杂度分析

解法一

遍历数组一次，每个位置只做常数次计算。

• 时间复杂度：O(n)
• 空间复杂度：O(n)

解法二

同样只遍历数组一次。

滚动变量只使用常数个额外变量。

• 时间复杂度：O(n)
• 空间复杂度：O(1)

解法二空间更优，是推荐写法。