leetcode：1567. 乘积为正数的最长子数组长度【dp[i]表示以i结尾的最大长度】

分析

同样的，我们需要最长负数和最长正数的乘积的最大长度
其中dp[i]表示选了第i个情况下的最大长度
然后我们可以推导positive[i + 1]和negative[i + 1]的关系式子

if nums[i] > 0:
   positive[i] = positive[i - 1] + 1
   negative[i] = (negative[i - 1] + 1 if negative[i - 1] > 0 else 0)
elif nums[i] < 0:
   positive[i] = (negative[i - 1] + 1 if negative[i - 1] > 0 else 0)
   negative[i] = positive[i - 1] + 1
else:
   positive[i] = negative[i] = 0

若当前是正数：
positive[i]直接是上一个+1即可
negative[i]的话，如果之前并没有negative的话，乘一个整数也不会是negative，所以是0；如果有的话就+1
若当前是负数：
negative[i]的话直接上一个正数+1
positive[i]的话如果之前没有负数，当前也整不成正数，如果有的话，直接+1
若当前是0
两个重置0

ac code

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        length = len(nums)
        positive, negative = [0] * length, [0] * length
        if nums[0] > 0:
            positive[0] = 1
        elif nums[0] < 0:
            negative[0] = 1
        
        maxLength = positive[0]
        for i in range(1, length):
            if nums[i] > 0:
                positive[i] = positive[i - 1] + 1
                negative[i] = (negative[i - 1] + 1 if negative[i - 1] > 0 else 0)
            elif nums[i] < 0:
                positive[i] = (negative[i - 1] + 1 if negative[i - 1] > 0 else 0)
                negative[i] = positive[i - 1] + 1
            else:
                positive[i] = negative[i] = 0
            maxLength = max(maxLength, positive[i])

        return maxLength


        

总结

dp[i]表示以i结尾的最长xxx
这里同时考虑正负两种情况