Leetcode-D6-152. 乘积最大子数组&1567. 乘积为正数的最长子数组长度

【前几天太忙了+打乒乓球+精神状态不好,一直拖拖拖,拖到了今天,继续打卡】

152. 乘积最大子数组

1、这题还是没什么思路,想得到了递归,但是分类讨论的时候模模糊糊,说不清楚,于是去看了答案。
2、答案的思路要清晰一点。
(1)乘积最大子数组是max{前面乘积最大nums[i],nums[i]},即一种是连续乘的情况,一种是断开单算的情况,找一个最大的。
(2)在连续乘的情况中,如果nums[i]是负数,那么之前连续乘最小的与nums[i]相乘,就是目前连续乘最大的。也就是说,如果nums[i]是正数,那么连续乘最大的就是nums[i]乘之前的连续乘最大;如果nums[i]是负数,那么连续乘最大就是nums[i]之前连续乘最小。
(3)用imin记录当前连续乘的最小值;imax记录当前连续乘的最大值;
if nums[i]>0,Imax=max{imax
nums[i],nums[i]},imin=min{imin
nums[i],nums[i]};if nums[i]<0,imax=max{iminnums[i],nums[i]},imin = min{imaxnums[i],nums[i]}
3、第一次出错了,原因是没有考虑在交换值的时候imax的值也改变了

    def maxProduct(self, nums: List[int]) -> int:
        
        imax = nums[0]
        imin = nums[0]
        n = len(nums)
        result = [0]*n
        result[0] = imax
        for i in range(1,n):
            if nums[i]>=0:
                imax = max(imax*nums[i],nums[i])
                imin = min(imin*nums[i],nums[i])
                result[i] = imax
            if nums[i]<0:
                imax = max(imin*nums[i],nums[i])
                imin = min(imax*nums[i],nums[i])
                result[i] = imax
        return max(result)

4、更改一下,加个temp
def maxProduct(nums):
imax = nums[0]
imin = nums[0]
n = len(nums)
result = [0]n
result[0] = imax
for i in range(1,n):
if nums[i]>=0:
imax = max(imax
nums[i],nums[i])
imin = min(iminnums[i],nums[i])
result[i] = imax
if nums[i]<0:
temp = imax
imax = max(imin
nums[i],nums[i])
imin = min(temp*nums[i],nums[i])
result[i] = imax
return max(result)

print(maxProduct([-4,-3,-2]))
成功!!!

1567. 乘积为正数的最长子数组长度

1、仍旧没思路。遍历一遍,记录下0和负数的位置。
2、看了答案,有些不理解,为什么要分类讨论negative[i-1]/positive[i-1]是否为0,敲了代码意识到:比如,之前为negative[i-1]=0,则以i-1为结尾的负乘积的元素个数为0,那么当nums[i]>0的时候,与前面相乘并不能有负数生成,negative[i]的长度并不会加1;同理,如果positive[i-1]=0,即以i-1结尾的正乘积的元素个数为0,那么当nums[i]<0时,相乘,negative[i]的个数并不是positive[i-1]+1,因为原来没有positive[i]

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        #以i为结尾的最长正数子数组和最长负数子数组
        n = len(nums)
        positive = [0]*n
        negative = [0]*n
        if nums[0]>0:
            positive[0]=1
        elif nums[0]<0:
            negative[0]=1
        for i in range(1,n):
            if nums[i]>0:
                positive[i] = positive[i-1]+1
                negative[i] = (negative[i - 1] + 1 if negative[i-1]!=0 else 0)
            if nums[i]==0:
                positive[i] = 0
                negative[i] = 0
            if nums[i]<0:
                positive[i] = (negative[i-1]+1 if negative[i-1]!=0 else 0)
                negative[i] = positive[i-1]+1

        return max(positive)

Leetcode-D6-152. 乘积最大子数组&1567. 乘积为正数的最长子数组长度

上一篇:单调约束


下一篇:1008 Elevator (20 分)2021-11-01