[LC 1567] Maximum Length of Subarray With Positive Product

LeetCode 1567

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: 4
Explanation: The array nums already has a positive product of 24.

Since this is an optimization problem (what is the max subarray length at each step), this can be solved using dynamic programming. Let’s look at the bottom-up approach.

When we encounter a negative number, it can suddenly make the product of the entire subarray negative. The opposite is true for negative subarrays. It has a “toggling” effect on the entire subarray. So at each step, we’ll keep track of the max subarray length for both positive and negative ones. And when we encounter a 0, we’ll just reset the length of both. Because we want the max length of a positive subarray, we’ll keep track of its max value.

Let’s look at an example step by step.

# input:    1, 1,-1, 1,-1, 0,-1, 1, 1,-1
# posLen:   1, 2, 0, 1, 5, 0, 0, 1, 2, 4
# negLen:   0, 0, 3, 4, 2, 0, 1, 2, 3, 3
# maxLen:   1, 2, 2, 2, 5, 5, 5, 5, 5, 5

So here is the basic scenario:

• If it’s positive, increase the positive length
  • If there is a negative number, increase the negative length (since adding a positive number to a negative number still results in a negative product)
• If it’s negative, flip the positive and negative lengths (since it “toggles” the subarrays), then increase the negative length
  • If there is no positive number, don’t increase the positive length (think of the case where 1st value is a negative number)
• If it’s a zero, reset the lengths

Here’s the implementation in python:

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        posLen = negLen = maxLen = 0

        for i in range(len(nums)):
            if nums[i] == 0:    # reset
                posLen = negLen = 0
                
            elif nums[i] > 0: 
                posLen += 1
                if negLen:
                    negLen += 1
                    
            elif nums[i] < 0: 
                posLen, negLen = negLen, posLen 
                negLen += 1
                if posLen:
                    posLen += 1
                    
            maxLen = max(maxLen, posLen)
        return maxLen

Time: O(n)
Space: O(1)