LeetCode88 - 乘积最大子数组

📝 题目描述

题目链接：乘积最大子数组

给你一个整数数组 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-位 整数

💡 解题思路

方法一：动态规划

如果我们用 $f_{max}​(i)$ 开表示以第 $i$ 个元素结尾的乘积最大子数组的乘积，$a$ 表示输入参数 $nums$，那么根据“最大子数组和”的经验，我们很容易推导出这样的状态转移方程：

$$f_{max}​(i) = max_{i=1}^{n} \{f(i−1)×a_i​,a_i \}$$

它表示以第 $i$ 个元素结尾的乘积最大子数组的乘积可以考虑 $a_i$​ 加入前面的 $f_{max}​(i−1)$ 对应的一段，或者单独成为一段，这里两种情况下取最大值。求出所有的 $f_{max}​(i)$ 之后选取最大的一个作为答案。

但在这里，这样做是错误的。因为这里的定义并不满足“最优子结构”。具体地讲，如果 $a=\{5,6,−3,4,−3\}$，那么此时 $f_{max}$​ 对应的序列是 $\{5,30,−3,4,−3\}$，按照前面的算法我们可以得到答案为 $30$，即前两个数的乘积，而实际上答案应该是全体数字的乘积。问题出在最后一个 $−3$ 所对应的 $f_{max}$​ 的值既不是 $−3$，也不是 $4×−3$，而是 $5×30×(−3)×4×(−3)$。所以我们得到了一个结论：当前位置的最优解未必是由前一个位置的最优解转移得到的。

我们可以根据正负性进行分类讨论。

考虑当前位置如果是一个负数的话，那么我们希望以它前一个位置结尾的某个段的积也是个负数，这样就可以负负得正，并且我们希望这个积尽可能“负得更多”，即尽可能小。如果当前位置是一个正数的话，我们更希望以它前一个位置结尾的某个段的积也是个正数，并且希望它尽可能地大。于是这里我们可以再维护一个 $f_{min}​(i)$，它表示以第 $i$ 个元素结尾的乘积最小子数组的乘积，那么我们可以得到这样的动态规划转移方程：

$$f_{\max}(i)=\max_{i=1}^n\{f_{\max}(i-1)\times a_i,f_{\min}(i-1)\times a_i,a_i\} \\ f_{\min}(i)=\min_{i=1}^n\{f_{\max}(i-1)\times a_i,f_{\min}(i-1)\times a_i,a_i\}$$

它代表第 $i$ 个元素结尾的乘积最大子数组的乘积 $f_{max}​(i)$，可以考虑把 $a_i$​ 加入第 $i−1$ 个元素结尾的乘积最大或最小的子数组的乘积中，二者加上 $a_i$​，三者取大，就是第 $i$ 个元素结尾的乘积最大子数组的乘积。第 $i$ 个元素结尾的乘积最小子数组的乘积 $f_{min}​(i)$ 同理。

方法二：优化后的动态规划

由于第 $i$ 个状态只和第 $i−1$ 个状态相关，根据“滚动数组”思想，我们可以只用两个变量而非两个数组来维护 $i−1$ 时刻的状态，一个维护 $f_{max}$​，一个维护 $f_{min}$​。

🔧 代码实现

1、动态规划

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector<int> max_dp(nums.size(), 0);
        vector<int> min_dp(nums.size(), 0);
        max_dp[0] = nums[0];
        min_dp[0] = nums[0];

        for(int i = 1; i < nums.size(); i++) {
            max_dp[i] = max({nums[i], max_dp[i - 1]*nums[i], min_dp[i - 1]*nums[i]});
            min_dp[i] = min({nums[i], max_dp[i - 1]*nums[i], min_dp[i - 1]*nums[i]});
        }

        return *max_element(max_dp.begin(), max_dp.end());
    }
};

2、优化后的动态规划

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int max_dp = nums[0], min_dp = nums[0], res = nums[0];

        for(int i = 1; i < nums.size(); i++) {
            int temp = max_dp;
            max_dp = max({nums[i], max_dp*nums[i], min_dp*nums[i]});
            min_dp = min({nums[i], temp*nums[i], min_dp*nums[i]});
            res = max(res, max_dp);
        }

        return res;
    }
};

📊 复杂度分析

1、动态规划

• 时间复杂度：$O(n)$，程序一次循环遍历了 nums。
• 空间复杂度：$O(n)$，需要存储额外的两个 dp 数组。

2、优化后的动态规划

• 时间复杂度：$O(n)$，程序一次循环遍历了 nums。
• 空间复杂度：$O(1)$，优化后只使用常数个临时变量作为辅助空间，与 $n$ 无关。

🎯 总结

• 核心思想：思路转换，从“最大子数组和”迁移到本题的特殊情况。