题目链接：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个奇数，它可以选择该区间内第一个奇数及其左边部分，也可以选择最后一个奇数及其右边部分。但这道题目需要注意一些边界特殊条件。

4.代码

class Solution(object):def get_qz_j(self,nums):qz,res=[],1for i in nums:res*=iqz.append(res)return qzdef get_qz_fs(self,nums):res,qz_fs=1,0for i in nums:res*=iif i<0:return resreturn 1def get_hz_fs(self,nums):res=1for i in range(len(nums)-1,-1,-1):res*=nums[i]if nums[i]<0:return resreturn 1def 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),1ans=qz_j[len(nums)-1]cnt,id1=0,0for i in range(len(nums)):if nums[i] <0:cnt+=1id1=iif cnt%2==0:return ansif 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 ansdef get_max_sum(self,nums):flag,ans,last=0,-1000000000,0for i in range(len(nums)):if nums[i]==0:flag=1if i!=last:ans=max(ans,self.get_max(nums[last:i]))last=i+1ans=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 ansdef maxProduct(self, nums):return self.get_max_sum(nums)