博客

乘积最大子数组

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

示例 1:


输入: [2,3,-2,4]

输出: 6

解释: 子数组 [2,3] 有最大乘积 6。

示例 2:


输入: [-2,0,-1]

输出: 0

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

思路：


方法一：

1. 对每个元素求出最大连续乘积。
2. 将所有元素的最大连续乘积进行比较，求出最大值。

方法二：动态规划

最小值乘一个负数，则可能成为最大值。

最大值乘一个正数，则可能成为最大值。

1. 从第一个元素至第i个元素的子数组最大连续乘积，可能为第i-1个元素的子数组最大值乘以
   
   第i个元素（正数）
   
   ，第i-1个元素的子数组最小值乘以
   
   第i个元素（负数）
   
   ，第i个元素。即
   
   max_sub_arr[i]=max(max_sub_arr[i-1]*nums[i], min_sub_arr[i-1]*nums[i], nums[i])
2. 同理，子数组最小连续乘积，可能为第i-1个元素的子数组最大值乘以
   
   第i个元素（负数）
   
   ，第i-1个元素的子数组最小值乘以
   
   第i个元素（正数）
   
   ，第i个元素。
   
   min_sub_arr[i]=min(max_sub_arr[i-1]*nums[i], min_sub_arr[i-1]*nums[i], nums[i])

代码：


方法一：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int cur_max=INT_MIN,max_multi,multi ,size;
        size=nums.size();
        for(int i=0;i<size;i++)
        {
            multi=nums[i];   
            max_multi=nums[i];  
            for(int j=i+1;j<size;j++)
            {
                multi*=nums[j];   //当前连续乘积
                max_multi=max_multi>multi?max_multi:multi;   //单个元素的最大连续乘积
            }
            cur_max=cur_max>max_multi?cur_max:max_multi;   //所有元素的最大连续乘积
        }
        return cur_max;
    }
};

方法二：动态规划

//方法二：动态规划
    int maxProduct(vector<int>& nums) {
        int cur_max;
        vector<int> max_sub_arr(nums.size(),0),min_sub_arr(nums.size(),0);
        max_sub_arr[0]=nums[0];
        min_sub_arr[0]=nums[0];
        
        cur_max=max_sub_arr[0];
        for(int i=1;i<nums.size();i++)
        {
            max_sub_arr[i]=max(max_sub_arr[i-1]*nums[i],min_sub_arr[i-1]*nums[i]);
            max_sub_arr[i]=max(max_sub_arr[i],nums[i]);
            min_sub_arr[i]=min(max_sub_arr[i-1]*nums[i],min_sub_arr[i-1]*nums[i]);
            min_sub_arr[i]=min(min_sub_arr[i],nums[i]);
            cur_max=cur_max>max_sub_arr[i]?cur_max:max_sub_arr[i];
        }        
        return cur_max;             
    }

结果：

方法一：用时以及内存消耗都较大



方法二：动态规划，可以看出用时明显减少。




参考链接：


[1]

xiaoju233：乘积最大子数组 【动态规划】