Maximum Length of Subarray With Positive Product

Published: Sep 10, 2022

Medium Dynamic Programming Array


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.

Problem Description

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
                pos, neg = neg + 1 if neg > 0 else 0, pos + 1
            max_v = max(max_v, pos)
        return max_v


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