Leetcode-D23-动态规划(二刷)-152. 乘积最大子数组&1567. 乘积为正数的最长子数组长度

Leetcode-D23-动态规划(二刷)-152. 乘积最大子数组&1567. 乘积为正数的最长子数组长度 152. 乘积最大子数组

1、用的dp，但考虑到乘积的正负没法直接用，卡了一下。突然想起来之前用过两个dp，一个记录负乘积一个记录正乘积。先记录个想法，我去请个假。
2、
写了一下，不太对。

    n = len(nums)
    dp_f = [-1] +[0]*n
    dp_z = [1]+[0]*n
    for i in range(1,n+1):
        if nums[i]>0:
            dp_z[i] = max(dp_z[i-1]*nums[i],nums[i])
            dp_f[i] = dp_f[i-1]*nums[i]
        if nums[i]<0:
            dp_z[i] = dp_f[i-1]*nums[i]
            dp_f[i] = min(dp_z[i-1]*nums[i],nums[i])
        if nums[i]==0:
            dp_z[i]=0
            dp_f[i]=0
    return dp_z[n]

我发现不好初始化dp_f[0]=-1，这样有一个正的就会增大dp_f，而实际上并不能取到。有点困了，回家好好做吧、
3、酒足饭饱，吃了羊蝎子、盘挞和其他东西，现在要写题啦~
用脑子改了一下，过了，但是不够完美，看个答案吧~
我用了两个dp，分别记录以nums【n】结尾的最大正、负连乘。当nums【n+1】是整数的时候，那dp_z【n+1】=max（nums【n+1】，nums【n+1】*dp【n】）因为有可能dp【n】=0，所以取个max，至于dp_f[n+1]，就等于dp_f[n]*nums[n+1],无论dp_f【n】是负是0，都满足。同理nums[n+1]<0的情况。初始化就初始化dp_f/z[0]=0即可。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:   
        n = len(nums)
        if n==1:
            return nums[0]
        dp_f =[0]*(n+1)
        dp_z = [0]*(n+1)
        for i in range(1,n+1):
            if nums[i-1]>0:
                dp_z[i] = max(dp_z[i-1]*nums[i-1],nums[i-1])
                dp_f[i] = dp_f[i-1]*nums[i-1]
            if nums[i-1]<0:
                dp_z[i] = dp_f[i-1]*nums[i-1]
                dp_f[i] = min(dp_z[i-1]*nums[i-1],nums[i-1])
            if nums[i-1]==0:
                dp_z[i]=0
                dp_f[i]=0
        return max(dp_z)

4、看了答案，两个dp不理解为正负，理解为当前最小最大应该更好一些。

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

1、有思路了，去试一下
2、没看出来哪里错了呀

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        dp_z = [0]*(n+1)
        dp_f = [0]*(n+1)

        for i in range(1,n+1):
            if nums[i-1]>0:
                dp_z[i] = dp_z[i-1]+1
                if dp_f[i-1]==0:
                    dp_f[i]=0
                if dp_f[i-1]>0:
                    dp_f[i]+=1
            if nums[i-1]<0:
                dp_f[i] = dp_z[i-1]+1
                if dp_f[i-1]==0:
                    dp_z[i]=0
                if dp_f[i-1]>0:
                    dp_z[i] = dp_f[i-1]+1
            if nums[i-1]==0:
                dp_f[i]=0
                dp_z[i]=0

            return max(dp_z)

鹅鹅鹅应该是return的indent不太对
3、除了这个，还有一行代码写的不对

                    dp_f[i] = dp_f[i-1]+1

之前写成dp_f[i] +=1了。
这个应该是如果之前dp_f[i-1]>0，乘上一个正数，此时dp_f[i]就会等于dp_f[i-1]+1。如果等于0的话，意味着之前连续乘积没有负数，那再乘一个正数，也不会有负数，那dp_f[i]就仍为0.

今天题先做到这里啦~回家的感觉真好！！！我去搞搞毕业设计!