# Maximum Length of Subarray With Positive Product

Published: Sep 10, 2022

Medium Dynamic Programming Array

## Introduction

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.

Constraints:

• `1 <= nums.length <= 10**5`
• `-10**9 <= nums[i] <= 10**9`

https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/

## Examples

``````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].
``````

## Analysis

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.

## Solution

``````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
``````

## Complexities

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