[数据结构与算法]【Leetcode】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 * 104
• -10 <= nums[i] <= 10
• nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

解题思路

这是一个动态规划的题目，状态表示比较常规，但是状态计算时有细节需要注意，总体来看这题还是不简单的。

题意很好理解，找到乘积最大的非空连续子数组，需要注意的是连续，并且最大，还需要注意的是数组的数据范围是-10 <= nums[i] <= 10，所以还需要处理正负的问题。

状态表示

先来说说状态表示，因为是连续，所以可以以子数组的最后一位元素来作为表示。$dp(x)$表示以第i位作为连续子数组最后一位元素的所有子数组的集合，$dp[i]$表示dp(x)集合中的所有子数组的乘积的最值。

状态计算

再来看看状态计算，状态计算是需要注意的，由于存在负数的情况，所以需要考虑到，最大值如果是正数乘以一个负数直接变成了最小值，而对应的一个最小值如果是负数乘以一个负数，直接就变成了最大值，还有0的情况，任何数乘以0都是0。所以综上来就看，需要维护两个值，一个最大值，一个最小值。$dpmax[i],dpmin[i]$分别维护最大值和最小值。

所以整体的最大值就是$dpmax[i]=max(nums[i],dpmax[i?1]?nums[i])$，最小值就是$dpmin[i]=min(nums[i],dpmin[i?1]?nums[i])$。

如果数组元素都是正数确实可以这样表示，但是存在负数和0的情况，所以这样写是不对的。

考虑上负数和0的情况，状态方程也就需要发生改变，状态方程变成了$dpmax[i]=max(nums[i],max(dpmax[i?1]?nums[i],dpmin[i?1]?nums[i])$， $dpmin[i]=min(nums[i],min(dpmax[i?1]?nums[i]),dpmin[i?1]?nums[i])$。

代码实现

class Solution
{
public:
    int maxProduct(vector<int> &nums)
    {
        const int N = 2 * 1e4 + 10;
        int dpmin[N], dpmax[N];
        int res = nums[0];
        //初始化dp数组，初始化为nums[0]
        dpmax[0] = nums[0], dpmin[0] = nums[0]; 
        //从第二个元素开始循环
        for (int i = 1; i < nums.size(); i++)
        {
            dpmax[i] = max(nums[i], max(dpmin[i - 1] * nums[i], dpmax[i - 1] * nums[i])); //记录最大值
            dpmin[i] = min(nums[i], min(dpmin[i - 1] * nums[i], dpmax[i - 1] * nums[i])); // 记录最小值
            //求出最大值
            res = max(res, dpmax[i]);
        }
        return res;
    }
};