152. 乘积最大子数组

给你一个整数数组 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 * 104
• -10 <= nums[i] <= 10
• nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

方法一：动态规划

可视化演示

以 nums = [2, 3, -2, 4] 为例，演示动态规划：同时维护以 nums[i] 结尾的最大乘积与最小乘积（因为负数乘负数会反转大小）。蓝色为当前计算，绿色为已完成，红色为答案。点击 ▶ 播放，或逐步操作。

0

1

2

3

dp[i][0] 最大积

2

dp[i][1] 最小积

2

当前计算比较/参照已计算回溯路径答案

初始化 i=0：dp[0][0] = dp[0][1] = nums[0] = 2，ans = 2。同时维护最大积与最小积，是因为负数乘负数会反转大小。

1 / 5 速度 1000ms

跳过可视化，直接看代码 ↓

Java

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int ans = nums[0];
        int[][] dp = new int[n][2];
        dp[0][0] = nums[0];
        dp[0][1] = nums[0];

        for (int i = 1; i < n; i++) {
            // 最大值
            dp[i][0] = Math.max(nums[i], Math.max(dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i]));
            // 最小值
            dp[i][1] = Math.min(nums[i], Math.min(dp[i - 1][1] * nums[i], dp[i - 1][0] * nums[i]));
            ans = Math.max(dp[i][0], ans);
        }

        return ans;
    }
}

方法二：动态规划优化

我们定义两个变量 $f$ 和 $g$，其中 $f$ 表示以 $nums[i]$ 结尾的乘积最大子数组的乘积，而 $g$ 表示以 $nums[i]$ 结尾的乘积最小子数组的乘积。初始时 $f$ 和 $g$ 都等于 $nums[0]$。答案为所有 $f$ 中的最大值。

从 $i=1$ 开始，我们可以考虑将第 $i$ 个数 $nums[i]$ 添加到前面的乘积最大或者乘积最小的子数组乘积的后面，或者单独作为一个子数组乘积（即此时子数组长度只有 $1$）。我们将此前的乘积最大值记为 $ff$，乘积最小值记为 $gg$，那么 $f=max(f,ff\times nums[i],gg\times nums[i])$，而 $g=min(g,ff\times nums[i],gg\times nums[i])$。接下来，我们更新答案 $ans=max(ans,f)$，然后继续计算下一个位置。

最后的答案即为 $ans$。

时间复杂度 $O(n)$，其中 $n$ 是数组 $nums$ 的长度。我们只需要遍历数组一次即可求得答案。空间复杂度 $O(1)$。

可视化演示

以 nums = [2, 3, -2, 4] 为例，演示滚动变量优化：f 为最大乘积、g 为最小乘积，每次用旧值 ff、gg 推出新 f、g（因为负数乘负数会反转大小）。蓝色为当前计算，绿色为已完成，红色为答案。点击 ▶ 播放，或逐步操作。

i▼

f

20

·1

·2

·3

g

20

·1

·2

·3

nums

20

31

-22

43

当前计算比较/参照已计算回溯路径答案

初始化 i=0：f = g = ans = nums[0] = 2。f 为最大乘积，g 为最小乘积。

1 / 5 速度 1000ms

跳过可视化，直接看代码 ↓

Java

class Solution {
    public int maxProduct(int[] nums) {
        int f = nums[0], g = nums[0], ans = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            int ff = f, gg = g;
            f = Math.max(nums[i], Math.max(ff * nums[i], gg * nums[i]));
            g = Math.min(nums[i], Math.min(ff * nums[i], gg * nums[i]));
            ans = Math.max(ans, f);
        }
        return ans;
    }
}

C++

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int f = nums[0], g = nums[0], ans = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            int ff = f, gg = g;
            f = max({nums[i], ff * nums[i], gg * nums[i]});
            g = min({nums[i], ff * nums[i], gg * nums[i]});
            ans = max(ans, f);
        }
        return ans;
    }
};

TypeScript

function maxProduct(nums: number[]): number {
    let [f, g, ans] = [nums[0], nums[0], nums[0]];
    for (let i = 1; i < nums.length; ++i) {
        const [ff, gg] = [f, g];
        f = Math.max(nums[i], ff * nums[i], gg * nums[i]);
        g = Math.min(nums[i], ff * nums[i], gg * nums[i]);
        ans = Math.max(ans, f);
    }
    return ans;
}

Python

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = f = g = nums[0]
        for x in nums[1:]:
            ff, gg = f, g
            f = max(x, ff * x, gg * x)
            g = min(x, ff * x, gg * x)
            ans = max(ans, f)
        return ans