每日OJ题_子数组子串dp③_力扣152. 乘积最大子数组

目录

力扣152. 乘积最大子数组

解析代码

---

力扣152. 乘积最大子数组

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

class Solution {
public:
    int maxProduct(vector<int>& nums) {
 
    }
};

---

解析代码

这道题与最大子数组和非常相似，可以效仿着定义⼀下状态表示以及状态转移：

• dp[i] 表⽰以 i 为结尾的所有子数组的最大乘积，
• dp[i] = max(nums[i], dp[i - 1] * nums[i]) ；

        由于正负号的存在，很容易就可以得到，这样求 dp[i] 的值是不正确的。因为 dp[i -1] 的信息并不能让我们得到 dp[i] 的正确值。比如数组 [-2, 5, -2] ，用上述状态转移得到的 dp数组为 [-2, 5, -2] ，最大乘积为 5 。但是实际上的最大乘积应该是所有数相乘，结果为 20 。

        究其原因，就是因为我们在求 dp[2] 的时候，因为 nums[2] 是⼀个负数，因此我们需要的是i - 1 位置结尾的最小的乘积 （-10） ，这样⼀个负数乘以最小值，才会得到真实的最大值。

因此不仅需要一个乘积最大值的 dp 表，还需一个乘积最小值的 dp 表。这里用f和g数组表示：

• f[i] 表示：以 i 结尾的所有子数组的最大乘积。
• g[i] 表示：以 i 结尾的所有子数组的最小乘积。

状态转移方程：

        遍历每一个位置的时候，要同步更新两个 dp 数组的值。对于 f[i] ，也就是以 i 为结尾的所有字数组的最大乘积，对于所有子数组，可以分为下面三种形式：

• 子数组的长度为 1 ，也就是 nums[i] ；
• 子数组的长度大于 1 ，但 nums[i] > 0 ，此时需要的是 i - 1 为结尾的所有子数组的最大乘积 f[i - 1]，再乘上 nums[i] ，也就是 nums[i] * f[i - 1] ；
• 子数组的长度大于 1 ，但 nums[i] < 0 ，此时需要的是 i - 1 为结尾的所有子数组的最小乘积 g[i - 1]，再乘上 nums[i] ，也就是 nums[i] * g[i - 1] ；

（如果 nums[i] = 0 ，所有子数组的乘积均为 0 ，三种情况其实都包含了）

对于num[i] 可以分类讨论，也可以直接取最大值，这里直接取最大值：

综上所述， f[i] = max(nums[i], max(nums[i] * f[i - 1], nums[i] * g[i -1]) );

同理可得，g[i] = min(nums[i], min(nums[i] * f[i - 1], nums[i] * g[i - 1]));

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n), g(n); // 以i结尾的所有子数组的最大/小乘积
        int ret = f[0] = g[0] = nums[0];
        for(int i = 1; i < n; ++i)
        {
            f[i] = max(nums[i], max(nums[i] * f[i-1], nums[i] * g[i-1]));
            g[i] = min(nums[i], min(nums[i] * f[i-1], nums[i] * g[i-1]));
            ret = max(ret, f[i]);
        }
        return ret;
    }
};