Table of Contents
Open Table of Contents
Problem
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.
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.
Example 3:
Input: nums = [1,2,3,0,1]
Output: 2
Explanation: The longest subarray with positive product is [1,2] or [2,3].
Constraints:
1 <= nums.length <= 10^5
10^9 <= nums[i] <= 10^9
Explanation/Approach
The key to solving this problem is to realize that a subarray’s product is positive if it contains an even number of negative numbers. Zeroes reset the subarray as they make the product zero. We will use dynamic programming to solve this problem.
Dynamic Programming Approach:
 Track Positive and Negative Lengths: Keep track of the length of the subarray with a positive product (
positiveLength
) and the length of the subarray with a negative product (negativeLength
).  Iterate Over the Array: For each element in the array:
 If the element is positive, increment
positiveLength
. IfnegativeLength
is not zero, increment it too.  If the element is negative, swap
positiveLength
andnegativeLength
and then incrementnegativeLength
.  If the element is zero, reset both lengths to zero.
 If the element is positive, increment
 Update Maximum Length: After processing each element, update the maximum length of the subarray with a positive product.
Solution: Dynamic Programming
class Solution:
def getMaxLen(self, nums: List[int]) > int:
positiveLength, negativeLength = 0, 0
maxLength = 0
for num in nums:
if num > 0:
positiveLength += 1
negativeLength = negativeLength + 1 if negativeLength > 0 else 0
elif num < 0:
positiveLength = negativeLength + 1 if negativeLength > 0 else 0
negativeLength = positiveLength + 1
else:
positiveLength, negativeLength = 0, 0
maxLength = max(maxLength, positiveLength)
return maxLength
Time and Memory Complexity
 Time Complexity: O(n), where n is the length of
nums
. We iterate through the array once.  Memory Complexity: O(1), as we only use a few variables for tracking lengths and do not use any additional data structures.
Visual Representation
Consider the input nums = [0,1,2,3,4]
.

Iterate through the array:
 Start with
positiveLength = 0
,negativeLength = 0
.  For
1
(positive),positiveLength = 1
,negativeLength = 0
.  For
2
(negative), swap lengths,positiveLength = 0
,negativeLength = 2
.  For
3
(negative), swap lengths again,positiveLength = 3
,negativeLength = 0
.  For
4
(negative), swap lengths,positiveLength = 0
,negativeLength = 4
.
 Start with

Maximum Length Update:
 The maximum
positiveLength
observed is 3, which is the length of the subarray[1,2,3]
.
 The maximum