leetcode 152. 乘积最大子数组-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 152. 乘积最大子数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接：leetcode 152

1.题目

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

测试用例的答案是一个 32-位整数。

子数组是数组的连续子序列。

2.示例

1）示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

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

3）提示:
1 <= nums.length <= 2 * 10^4
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都保证是一个 32-位整数

3.分析

首先考虑数组中的特殊情况，也就是包含0 的情况，当所有子树组中包含0时，那么子树组乘积结果均为0。可以考虑以0作为分割标准分割出子树组。那么对于分割后的子树组，当我们考虑负数的情况，当区间内只有一个负数时，子树组乘积取最大只能是它左边的正数乘积，或者它右边的正数乘积（或者它自己）。当区间内包含多个（cnt）负数时，当cnt为偶数时，结果就是该树组本身乘积。当cnt为奇数时，对于第i个奇数，它可以选择该区间内第一个奇数及其左边部分，也可以选择最后一个奇数及其右边部分。但这道题目需要注意一些边界特殊条件。文章来源地址https://www.toymoban.com/news/detail-438523.html

4.代码

class Solution(object):
    def get_qz_j(self,nums):
        qz,res=[],1
        for i in nums:
            res*=i
            qz.append(res)
        return qz
    def get_qz_fs(self,nums):
        res,qz_fs=1,0
        for i in nums:
            res*=i
            if i<0:
                return res
        return 1
    def get_hz_fs(self,nums):
        res=1
        for i in range(len(nums)-1,-1,-1):
            res*=nums[i]
            if nums[i]<0:
                return res
        return 1
    def get_max(self,nums):
        qz_j=self.get_qz_j(nums)
        qz_fs,hz_fs,res=self.get_qz_fs(nums),self.get_hz_fs(nums),1
        ans=qz_j[len(nums)-1]
        cnt,id1=0,0
        for i in range(len(nums)):
            if nums[i] <0:
                cnt+=1
                id1=i
        if cnt%2==0:
            return ans
        if cnt==1:
            if id1!=0:
                ans=max(ans,qz_j[len(nums)-1]/hz_fs)
            if id1!=len(nums)-1:
                ans=max(ans,qz_j[len(nums)-1]/qz_fs)
        else:
            ans=max(ans,qz_j[len(nums)-1]/qz_fs)
            ans=max(ans,qz_j[len(nums)-1]/hz_fs)
        return ans
    def get_max_sum(self,nums):
        flag,ans,last=0,-1000000000,0
        for i in range(len(nums)):
            if nums[i]==0:
                flag=1
                if i!=last:
                    ans=max(ans,self.get_max(nums[last:i]))
                last=i+1
                ans=max(ans,0)
        if flag==0:
            return self.get_max(nums)
        if last<=len(nums)-1:
            ans=max(ans,self.get_max(nums[last:len(nums)]))
        return ans
    def maxProduct(self, nums):
        return self.get_max_sum(nums)