Leetcode-Medium 152. Maximum Product Subarray

致Great

发布于 2019-03-06 16:29:25

4660

题目描述

给定一个整数数组nums（有正有负），求最大子数组乘积

思路

求最大子数组乘积问题是求最大子数组之和演变而来，不过比求和更复杂一些。一个数相加于0不变，相加于一个负数变小；一个数与0相乘变为0，一个数与负数相乘有可能变大有可能变小。那么假设maxval[i]是以nums[i]结尾的最大子数组乘积，minval是以nums[i]结尾的最小子数组乘积，那么此时的最大值和最小值产生于maxval[i-1]*nums[i]，minval[i-1]*nums[i]和nums[i]这三个数之间。我们用maxval[i]记录最大子数组乘积，minval[i]记录最小子数组乘积，用maxval[i]更新最大值res

代码实现

class Solution:
    def maxProduct(self, nums: 'List[int]') -> 'int':
        ## 暴力求解
        # maxp=nums[0]
        # for i in range(len(nums)):
        #     curp=1
        #     for j in range(i,len(nums)):
        #         curp*=nums[j]
        #         if curp>maxp:
        #             maxp=curp
        # return maxp
        
        
        # B=nums[::-1]
        # for i in range(1,len(nums)):
        #     nums[i]*=nums[i-1] or 1
        #     B[i]*=B[i-1] or 1
        # return max(nums+B)
        
        # def swap(a,b):
        #     return b,a
        # minval=maxval=res=nums[0]
        # for val in nums[1:]:
        #     if val<0:
        #         minval,maxval=swap(minval,maxval)
        #     maxval=max(val,val*maxval)
        #     minval=min(val,val*minval)
        #     res=max(res,maxval)
            
        
        # minval=maxval=[0]*len(nums) # 报错
        minval=[0]*len(nums) 
        maxval=[0]*len(nums)
        minval[0]=maxval[0]=res=nums[0]
        for i in range(1,len(nums)):
            maxval[i]=max(nums[i],nums[i]*maxval[i-1],nums[i]*minval[i-1])
            minval[i]=min(nums[i],nums[i]*maxval[i-1],nums[i]*minval[i-1])
            res=max(res,maxval[i])
        return res

其他思路

当nums[i]<0的时候，交换最大值和最小值

class Solution:
    def maxProduct(self, nums: 'List[int]') -> 'int':
        def swap(a,b):
            return b,a
        minval=maxval=res=nums[0]
        for val in nums[1:]:
            if val<0:
                minval,maxval=swap(minval,maxval)
            maxval=max(val,val*maxval)
            minval=min(val,val*minval)
            res=max(res,maxval)
        return res

在讨论区看到了一个天秀的代码

class Solution:
    def maxProduct(self, nums: 'List[int]') -> 'int':
        B=nums[::-1]
        for i in range(1,len(nums)):
            nums[i]*=nums[i-1] or 1
            B[i]*=B[i-1] or 1
        return max(nums+B)

nums[i-1] or 1意思就是：if nums[i-1]!=0:return nums[i-1] else :return 1

暴力求解

class Solution:
    def maxProduct(self, nums: 'List[int]') -> 'int':
        # 暴力求解
        maxp=nums[0]
        for i in range(len(nums)):
            curp=1
            for j in range(i,len(nums)):
                curp*=nums[j]
                if curp>maxp:
                    maxp=curp
        return maxp

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019.02.22 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度

Leetcode-Medium 152. Maximum Product Subarray

Leetcode-Medium 152. Maximum Product Subarray

题目描述

思路

代码实现

其他思路

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐