Published: Sep 10, 2022

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