[leetcode] 1567. Maximum Length of Subarray With Positive Product

[leetcode] 1567. Maximum Length of Subarray With Positive Product

Description

Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

Return the maximum length of a subarray with positive product.

Example 1:

Input: nums = [1,-2,-3,4]Output: 4Explanation: The array nums already has a positive product of 24.

Example 2:

Input: nums = [0,1,-2,-3,-4]Output: 3Explanation: The longest subarray with positive product is [1,-2,-3] which has a product of 6.Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.

Example 3:

Input: nums = [-1,-2,-3,0,1]Output: 2Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].

Example 4:

Input: nums = [-1,2]Output: 1

Example 5:

Input: nums = [1,2,3,5,-6,4,0,10]Output: 4

Constraints:

1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9

分析

题目的意思是：给定一个数组，求出最长的非负乘积的子数组。首先子数组不包含0，所以可以按照0进行讨论，我参考了一下别人的实现。

pos_len记录乘积为正的长度，neg_len记录的是乘积为负的长度。遍历数组，如果当前的数为0，则pos_len和neg_len都为0。如果当前的数是负数，则pos_len和neg_len需要交换了，因为负数使得前面的累积子数组正负性发生了变化，然后neg_len和pos_len的长度加1。如果当前的数为正，则neg_len和pos_len的长度加1。上述加1的过程要区分为0的情况，因为需要考虑到前面遍历的子数组包含0的情况哈。遍历的时候维护更新res就能得到答案了。

代码

class Solution: def getMaxLen(self, nums: List[int]) -> int: pos_len=0 neg_len=0 res=0 for num in nums: if(num==0): pos_len,neg_len=0,0 elif(num<0): pos_len,neg_len=neg_len,pos_len neg_len+=1 if(pos_len>0): pos_len+=1 else: pos_len+=1 if(neg_len>0): neg_len+=1 res=max(res,pos_len) return res

参考文献

​​Leetcode 1567. Maximum Length of Subarray With Positive Product (python)​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。