LeetCode 152.乘积最大子序列(Maximum-Product-Subarray)

#@author:leacoder
#@des:  暴力求解  乘积最大子序列
# leetcode 超时

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        maxnum = float("-inf")
        for i in range(0,len(nums)):
            tmp = nums[i]
            for j in range(i+1,len(nums)):
                tmp *= nums[j]
                maxnum = max(maxnum,tmp)
            maxnum = max(maxnum,nums[i])
        return maxnum

#@author:leacoder
#@des:  动态规划  乘积最大子序列

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if nums is None : return 0
        imax = [0,0] 
        imin = [0,0]
        imax[0], imin[0],res= nums[0],nums[0],nums[0]
        
        for i in range(1,len(nums)):
            x,y=i%2,(i-1)%2 # x 表示当前最大或最小下标   y 表示前面最大或最小下标
            imax[x] = max( imax[y] * nums[i], imin[y] * nums[i], nums[i] ) 
            # nums[i]可能为负数，若为负数 前面最小 *  nums[i]变为最大，前面最大 *  nums[i]变为最小
            imin[x] = min( imax[y] * nums[i], imin[y] * nums[i], nums[i] ) 
            res = max(res,imax[x])
        return res

#@author:leacoder
#@des:  动态规划  乘积最大子序列

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if nums is None : return 0
        res , curMax, curMin = nums[0],nums[0],nums[0]
        for i in range(1,len(nums)):
            num = nums[i]
            curMax, curMin = curMax * num, curMin * num
            # 由于 num可能为负数 上面结果可能刚好反了, curMax * 负数变为 curMin 顾需要下面语句处理
            curMax,curMin = max(curMax,curMin,num),min(curMax,curMin,num)
            res = max(curMax,res)
        return res

#@author:leacoder
#@des:  动态规划  乘积最大子序列

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if nums is None : return 0
        res , curMax, curMin = nums[0],nums[0],nums[0]
        for i in range(1,len(nums)):
            num = nums[i]
            if num < 0 :
                curMax, curMin = curMin, curMax # 由于 num为负数 导致最大的变最小的，最小的变最大的,因此交换两个的值
            curMax = max(curMax*num,num)
            curMin = min(curMin*num,num)
            res = max(curMax,res)
        return res