152. 乘积最大子数组

题目来源:

https://leetcode-cn.com/problems/maximum-product-subarray/submissions/

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

示例 1:

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

输出: 6

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

示例 2:

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

输出: 0

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

解法

C++代码:

解法一:暴力破解(注:所有用例通过,时间超时,不能通过测试)

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int max = INT_MIN;
        int size = nums.size();
        if(size==1) return nums[0];
        for(int i=0;i<size;i++)
        {
            max = nums[i]>max?nums[i]:max;
            int mul = nums[i];
            for(int j=i+1;j<size;j++)
            {
                max = mul*nums[j]>max?mul*nums[j]:max;
                mul *= nums[j];
            }
        }
        return max;
    }
};

184 / 184 个通过测试用例

状态:超出时间限制

复杂度分析:

时间复杂度:O(n^2)

空间复杂度:O(1)


解法二:

分析:

如果没有负数和0,乘积最大子数组为整个数组。

case 1:如果仅包括负数

1).负数总个数为奇数个,假设为m个,si表示第i个奇数所在数组的下标,数组为{an},那么乘积最大子数组为{a1,a2,…..,asm} 或者 {as1,as1+1,…..,an}。

2).负数总个数为偶数个,乘积最大子数组仍为整个数组。

case 2: 如果包括0

乘积最大子数组为以0为分段点划分的各个子数组乘积最大的所对应的子数组。

上述分析可以得到一个结论:在没有0的情况下, 最大子数组一定是从某一端开始的

证明:∵

case 1:如果两边其他部分的乘积符号相同的话, 那么可以延伸到整个数组

case 2:如果乘积符号不同的话, 总可以延伸到正的乘积的部分的端点处

∴ 最大子数组一定是从某一端开始的,证毕

如果遇到0的话, 就跳过0重新计算。

实现:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int size = nums.size(),i,maxmum=1;
        int res=nums[0];
        for(i=0;i<size;i++)     //正向遍历
        {
            maxmum *= nums[i];
            res = max(maxmum,res);
            if(nums[i]==0)      //遇到0重新计算
                maxmum = 1;
        }
        maxmum = 1;
        for(i=size-1;i>=0;i--)  //逆向遍历
        {
            maxmum *= nums[i];
            res = max(maxmum,res);
            if(nums[i]==0)      //遇到0重新计算
                maxmum = 1;
        }
        return res;
    }
};

执行用时 :8 ms, 在所有 C++ 提交中击败了69.45%的用户

内存消耗 :11.7 MB, 在所有 C++ 提交中击败了6.25%的用户

复杂度分析:

时间复杂度:O(n)

空间复杂度:O(1)


解法三:动态规划

什么是动态规划?

动态规划算法的核心就是记住已经解决过的子问题的解.

​ 例如斐波那契数列就是一个很形象的例子,其第n项为第n-1和第n-2项的和,所以要求第n项,仅需求第n-1和第n-2项即可,也就是将问题转移为子问题,而子问题是我们能够解决的。

思路:

由题意,易推导出状态转移方程:

\[f_{max}(i) = \max_{i=1}^{n}\{f_{max}(i-1)*a_i,a_i\}\]

但是该状态转移方程存在问题,因为当前位置的最优解未必是由前一个位置的最优解转移得到的,例如取

\[a=\{5,6,-3,4,-3\}\]

此时对应的fmax对应的序列是

\[f_{max} = \{5,30,-3,4,-3\}\]

其原因是负数破坏了这种状态,因为正数乘以负数会变的很小,因此需要讨论正负性。

考虑当前位置如果是一个负数的话,那么我们希望以它前一个位置结尾的某个段的积也是个负数,这样就可以负负得正,并且我们希望这个积尽可能「负得更多」,即尽可能小。如果当前位置是一个正数的话,我们更希望以它前一个位置结尾的某个段的积也是个正数,并且希望它尽可能地大。

因此引入一个状态转移方程fmin(i),表示以第i个元素结尾的乘积最小子数组的乘积。

\[f_{max}(i) = \max_{i=1}^{n}\{f_{max}(i-1)*a_i,f_{min}(i-1)*a_i,a_i\}\] \[f_{min}(i) = \min_{i=1}^{n}\{f_{max}(i-1)*a_i,f_{min}(i-1)*a_i,a_i\}\]

实现:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector <int> fmax(nums), fmin(nums);
        for (int i = 1; i < nums.size(); ++i) {
            fmax[i] = max(fmax[i-1]*nums[i],max(nums[i],fmin[i-1]*nums[i]));
            fmin[i] = min(fmin[i-1]*nums[i],min(nums[i],fmax[i-1]*nums[i]));
        }
        return *max_element(fmax.begin(),fmax.end());//返回fmax数组中最大的元素
    }
};

执行用时 :8 ms, 在所有 C++ 提交中击败了69.45%的用户

内存消耗 :12 MB, 在所有 C++ 提交中击败了6.25%的用户

复杂度分析:

时间复杂度:O(n)

空间复杂度:O(n)