Problem Description

You are given an array of integers nums. Your task is to find the maximum length of a subarray where the product of all its elements is positive.

A subarray is defined as a consecutive sequence of zero or more values taken from the original array. For example, if nums = [1, -2, 3, -4], then [1], [-2, 3], and [3, -4] are all valid subarrays.

The product of a subarray is positive when:

• All elements in the subarray are positive, OR
• The subarray contains an even number of negative elements (and no zeros)

You need to return the maximum length among all possible subarrays that have a positive product.

For example:

• If nums = [1, -2, -3, 4], the subarray [-2, -3, 4] has length 3 and product 24 (positive), while [1, -2, -3] has length 3 and product 6 (positive). The maximum length would be 4 for the entire array [1, -2, -3, 4] which has product 24.
• If nums = [0, 1, -2, -3, -4], the subarray [-2, -3, -4] has length 3 and product -24 (negative), but [-2, -3] has length 2 and product 6 (positive). The maximum length of a positive product subarray would be 3.

Note that if the array contains a zero, it breaks the product calculation, so subarrays cannot span across zeros.

Intuition

The key insight is that the sign of a product depends on the count of negative numbers. An even count of negatives gives a positive product, while an odd count gives a negative product. Zeros reset everything since any product involving zero becomes zero.

As we traverse the array, at each position we need to track two things:

1. The longest subarray ending at the current position with a positive product
2. The longest subarray ending at the current position with a negative product

Why track both? Because when we encounter a negative number, these two lengths swap roles - a positive product becomes negative when multiplied by a negative number, and vice versa.

Consider what happens at each element:

• Positive number: A positive product stays positive (just extend it by 1), and a negative product stays negative (also extend by 1)
• Negative number: A positive product becomes negative, and a negative product becomes positive (they swap)
• Zero: Both lengths reset to 0 since we can't continue any subarray through a zero

This leads us to use dynamic programming with two arrays:

• f[i]: length of longest positive-product subarray ending at index i
• g[i]: length of longest negative-product subarray ending at index i

The magic happens when we hit a negative number - if we had a negative-product subarray of length k ending at position i-1, multiplying by the current negative number gives us a positive-product subarray of length k+1 at position i. Similarly, a positive-product subarray becomes negative.

By tracking the maximum value of f[i] throughout our traversal, we find the longest subarray with a positive product.

Learn more about Greedy and Dynamic Programming patterns.

Solution Approach

We implement the solution using dynamic programming with two arrays f and g of length n:

• f[i] represents the length of the longest subarray ending at nums[i] with a positive product
• g[i] represents the length of the longest subarray ending at nums[i] with a negative product

Initialization:

• If nums[0] > 0: Set f[0] = 1 (we have a positive subarray of length 1), and g[0] = 0 (no negative subarray)
• If nums[0] < 0: Set f[0] = 0 (no positive subarray), and g[0] = 1 (we have a negative subarray of length 1)
• If nums[0] = 0: Both f[0] = 0 and g[0] = 0 (zero breaks any product)
• Initialize answer ans = f[0]

State Transition: For each index i from 1 to n-1, we update based on the value of nums[i]:

1. When nums[i] > 0:

   • f[i] = f[i-1] + 1 (positive stays positive, just extend by 1)
   • g[i] = 0 if g[i-1] == 0 else g[i-1] + 1 (if there was no negative subarray before, there still isn't; otherwise extend it)

2. When nums[i] < 0:

   • f[i] = 0 if g[i-1] == 0 else g[i-1] + 1 (negative × negative = positive, so we get positive from previous negative)
   • g[i] = f[i-1] + 1 (positive × negative = negative, so previous positive becomes negative)

3. When nums[i] = 0:

   • Both f[i] = 0 and g[i] = 0 (zero resets everything)

After processing each element, we update ans = max(ans, f[i]) to track the maximum length of a positive product subarray seen so far.

Example walkthrough with nums = [1, -2, -3, 4]:

• i=0: nums[0]=1>0, so f[0]=1, g[0]=0, ans=1
• i=1: nums[1]=-2<0, so f[1]=0, g[1]=f[0]+1=2, ans=1
• i=2: nums[2]=-3<0, so f[2]=g[1]+1=3, g[2]=f[1]+1=1, ans=3
• i=3: nums[3]=4>0, so f[3]=f[2]+1=4, g[3]=g[2]+1=2, ans=4

The final answer is 4, representing the entire array [1, -2, -3, 4] which has a positive product.

Example Walkthrough

Let's walk through the solution with nums = [2, -1, -3, 0, 5, -2].

We'll track two arrays:

• f[i]: length of longest positive-product subarray ending at index i
• g[i]: length of longest negative-product subarray ending at index i

Initial Setup:

• Arrays: f = [0, 0, 0, 0, 0, 0] and g = [0, 0, 0, 0, 0, 0]
• We'll update these as we process each element

Step-by-step processing:

i = 0, nums[0] = 2 (positive):

• Since it's positive: f[0] = 1 (single positive element)
• No negative product: g[0] = 0
• Update ans = 1
• State: f = [1, 0, 0, 0, 0, 0], g = [0, 0, 0, 0, 0, 0]

i = 1, nums[1] = -1 (negative):

• Previous positive becomes negative: g[1] = f[0] + 1 = 1 + 1 = 2
• No previous negative to make positive: f[1] = 0 (since g[0] = 0)
• ans remains 1
• State: f = [1, 0, 0, 0, 0, 0], g = [0, 2, 0, 0, 0, 0]

i = 2, nums[2] = -3 (negative):

• Previous negative becomes positive: f[2] = g[1] + 1 = 2 + 1 = 3
• Previous positive becomes negative: g[2] = f[1] + 1 = 0 + 1 = 1
• Update ans = max(1, 3) = 3
• State: f = [1, 0, 3, 0, 0, 0], g = [0, 2, 1, 0, 0, 0]

i = 3, nums[3] = 0 (zero):

• Zero resets everything: f[3] = 0, g[3] = 0
• ans remains 3
• State: f = [1, 0, 3, 0, 0, 0], g = [0, 2, 1, 0, 0, 0]

i = 4, nums[4] = 5 (positive):

• New positive number after zero: f[4] = f[3] + 1 = 0 + 1 = 1
• No negative product: g[4] = 0 (since g[3] = 0)
• ans remains 3
• State: f = [1, 0, 3, 0, 1, 0], g = [0, 2, 1, 0, 0, 0]

i = 5, nums[5] = -2 (negative):

• Previous positive becomes negative: g[5] = f[4] + 1 = 1 + 1 = 2
• No previous negative to make positive: f[5] = 0 (since g[4] = 0)
• ans remains 3
• State: f = [1, 0, 3, 0, 1, 0], g = [0, 2, 1, 0, 0, 2]

Final Result: The maximum length is 3, corresponding to the subarray [2, -1, -3] which has product 6 (positive).

The key observations:

1. When we hit -1 at index 1, the positive subarray [2] became negative [2, -1]
2. When we hit -3 at index 2, the negative subarray [2, -1] became positive [2, -1, -3] with length 3
3. The zero at index 3 prevented any subarray from spanning across it
4. After the zero, we started fresh but couldn't achieve a longer positive product subarray

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because the algorithm iterates through the array exactly once with a single for loop from index 1 to n-1, and within each iteration, it performs only constant-time operations (comparisons, assignments, and basic arithmetic operations).

The space complexity is O(n), where n is the length of the array nums. This is due to the allocation of two auxiliary arrays f and g, each of size n, to store the dynamic programming states. The array f[i] stores the maximum length of a subarray ending at index i with a positive product, while g[i] stores the maximum length of a subarray ending at index i with a negative product.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Zero Elements Properly

A common mistake is forgetting that zeros completely break the product chain. When encountering a zero, both positive and negative subarray lengths must reset to 0, not just continue from previous values.

Incorrect approach:

if current_num == 0:
    positive_length[i] = positive_length[i - 1]  # Wrong! Should be 0
    negative_length[i] = negative_length[i - 1]  # Wrong! Should be 0

Correct approach:

if current_num == 0:
    positive_length[i] = 0
    negative_length[i] = 0

2. Incorrect Initialization of Negative Length

When a negative number is encountered and there's no existing negative subarray (negative_length[i-1] == 0), developers might incorrectly set negative_length[i] = 0 instead of properly starting a new negative subarray.

Incorrect approach:

elif current_num < 0:
    positive_length[i] = negative_length[i - 1] + 1 if negative_length[i - 1] > 0 else 0
    negative_length[i] = positive_length[i - 1]  # Wrong! Forgets to add 1

Correct approach:

elif current_num < 0:
    positive_length[i] = negative_length[i - 1] + 1 if negative_length[i - 1] > 0 else 0
    negative_length[i] = positive_length[i - 1] + 1  # Always extends by 1

3. Space Optimization Pitfall

When optimizing space by using variables instead of arrays, a critical error occurs if you update both variables using the old values without storing them first.

Incorrect space-optimized approach:

for i in range(1, n):
    if nums[i] < 0:
        positive = negative + 1 if negative > 0 else 0
        negative = positive + 1  # Wrong! Uses updated positive value

Correct space-optimized approach:

for i in range(1, n):
    if nums[i] < 0:
        temp = positive  # Store old value first
        positive = negative + 1 if negative > 0 else 0
        negative = temp + 1  # Use the stored old value

4. Edge Case: Single Element Array

Failing to properly handle arrays with only one element, especially when that element is negative or zero.

Solution: The initialization step should correctly handle this:

• If nums = [-5], the answer should be 0 (no positive product subarray)
• If nums = [5], the answer should be 1
• If nums = [0], the answer should be 0

The provided code handles this correctly through proper initialization, but it's easy to overlook in custom implementations.