LeetCode每日一题5月18日 LeetCode152，乘积最大子数组

约定不等于承诺〃 2023-03-14 13:18 2阅读 0赞

## 问题描述： ##

给你一个整数数组 `nums` ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/maximum-product-subarray][https_leetcode-cn.com_problems_maximum-product-subarray]

示例 1:

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

示例 2:

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

## 解题思路： ##

这个和最大子序和有异曲同工之妙：[最大子序和][Link 1]

这是最大子序和的动态方程

![dp\[i+1\] = max(dp\[i\]+nums\[i+1\],nums\[i+1\])][dp_i_1_ _ max_dp_i_nums_i_1_nums_i_1]

本题也是使用动态规划，不过乘积会出现**负负得正的情况**，**因此我们需要统计俩个值，前部分的乘积的最大值，最小值**

假设**maxnum\[i\]代表从0-i的最大子序乘积**

**        minnum\[i\]代表从0-i的最小子序乘积（主要是用了统计负值）**

**则动态方程可以写成：![dp\[i+1\] = max(\{maxnum\[i\]\*num\[i+1\],minnum\[i\]\*num\[i+1\],num\[i+1\]\})][dp_i_1_ _ max_maxnum_i_num_i_1_minnum_i_num_i_1_num_i_1]**

**完整代码如下:**

class Solution {
    public:
        int maxProduct(vector<int>& nums) {
            int minnum=1,maxnum=1;
            int maxres = INT_MIN;
            for(int i=0;i<nums.size();i++){
                int aa = minnum*nums[i];
                int bb = maxnum*nums[i];
    
                minnum = min({nums[i],aa,bb});
                maxnum = max({nums[i],aa,bb});
    
                maxres = max(maxres,maxnum);
            }
            return maxres;
        }
    };

[https_leetcode-cn.com_problems_maximum-product-subarray]: https://leetcode-cn.com/problems/maximum-product-subarray
[Link 1]: https://blog.csdn.net/wuheng248113004/article/details/105899103
[dp_i_1_ _ max_dp_i_nums_i_1_nums_i_1]: https://private.codecogs.com/gif.latex?dp%5Bi&plus;1%5D%20%3D%20max%28dp%5Bi%5D&plus;nums%5Bi&plus;1%5D%2Cnums%5Bi&plus;1%5D%29
[dp_i_1_ _ max_maxnum_i_num_i_1_minnum_i_num_i_1_num_i_1]: https://private.codecogs.com/gif.latex?dp%5Bi&plus;1%5D%20%3D%20max%28%7Bmaxnum%5Bi%5D*num%5Bi&plus;1%5D%2Cminnum%5Bi%5D*num%5Bi&plus;1%5D%2Cnum%5Bi&plus;1%5D%7D%29