Published: Sep 10, 2022
When the problem asks maximum or minimum of something in the given array, it might be a dynamic programming problem. It’s not always, but good to consider dp solution. This problem keeps the state of positive/negative results length. The maximum length will be from positive length as the problem explains.
Given an array of integers
nums, find the maximum length of a subarray where the product of all its elements is positive. Return the maximum length of a subarray with positive product.
A subarray of an array is a consecutive sequence of zero or more values taken out of that array.
1 <= nums.length <= 10**5
-10**9 <= nums[i] <= 10**9
Example 1: Input: nums = [1,-2,-3,4] Output: 4 Explanation: The array nums already has a positive product of 24.
Example 2: Input: nums = [0,1,-2,-3,-4] Output: 3 Explanation: 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: 2 Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].
Two states, the length of positive/negative products will be used. When the value is 0, reset both states.
When the value is positive:
- increment positive length
- if negative length is greater than 0, increment negative length since positive value doesn’t flip pos/neg.
When the value is negative:
- flip pos/neg
- positive length is negative length plus one if it’s not 0
- negative length is positive length plus one
Additionally, compare maximum length with positive length in every iteration.
class MaximumLengthOfSubarrayWithPositiveProduct: def getMaxLen(self, nums: List[int]) -> int: pos, neg, max_v = 0, 0, 0 for num in nums: if num == 0: pos, neg = 0, 0 elif num > 0: pos += 1 neg = 0 if neg == 0 else neg + 1 else: pos, neg = neg + 1 if neg > 0 else 0, pos + 1 max_v = max(max_v, pos) return max_v