# Maximum Length of Subarray With Positive Product
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product)
Canonical: https://scaleengineer.com/dsa/problems/maximum-length-of-subarray-with-positive-product
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Arcesium](https://scaleengineer.com/companies/arcesium)
---
## Problem
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.

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

**Constraints:**

* `1 <= nums.length <= 105`
* `-109 <= nums[i] <= 109`

# Approaches
## Brute Force Approach
The brute-force approach is the most straightforward way to solve the problem. It involves generating every possible contiguous subarray, checking if the product of its elements is positive, and keeping track of the maximum length found. To avoid potential integer overflows from calculating the actual product, we only need to track the sign of the product. A zero in a subarray makes its product zero (not positive), and an even number of negative elements results in a positive product.
**Time:** O(n^2), where n is the number of elements in `nums`. The nested loops result in a quadratic number of operations as we check every possible subarray. · **Space:** O(1), as we only use a constant amount of extra space for variables like `maxLength` and `productSign`.
**Pros:** Simple to understand and implement.; Correctly solves the problem for smaller inputs.
**Cons:** The O(n^2) time complexity is too slow for the given constraints (n <= 10^5) and will likely result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
We can implement this using two nested loops. The outer loop iterates through all possible starting points `i` of a subarray, and the inner loop iterates through all possible ending points `j`. For each subarray `nums[i...j]`, we determine the sign of its product. Instead of re-computing the product for each subarray, we can maintain a running sign. When we extend the subarray from `nums[i...j-1]` to `nums[i...j]`, we update the sign based on `nums[j]`. If `nums[j]` is positive, the sign remains unchanged. If `nums[j]` is negative, the sign flips. If `nums[j]` is zero, the product becomes zero, and any longer subarray starting at `i` will also have a zero product, so we can stop extending from this `i`. If the sign of the current subarray's product is positive, we update our maximum length.

```java
class Solution {
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            int productSign = 1;
            for (int j = i; j < n; j++) {
                if (nums[j] == 0) {
                    // Product becomes 0, which is not positive.
                    // Any subarray extending further will also have a product of 0.
                    break; 
                } else if (nums[j] < 0) {
                    productSign *= -1;
                }
                
                // If product is positive, update maxLength
                if (productSign > 0) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength` to 0.
- Use a nested loop structure. The outer loop with index `i` defines the start of a subarray, and the inner loop with index `j` defines the end.
- For each subarray `nums[i...j]`, calculate the sign of its product.
- To do this efficiently, for a fixed `i`, as `j` increases, we can maintain the sign of the product of `nums[i...j]` in O(1) time.
- Initialize a variable `productSign = 1` before the inner loop.
- Inside the inner loop (for `j`):
  - If `nums[j]` is 0, the product becomes 0. No subarray starting at `i` and including `j` can have a positive product. So, we break the inner loop.
  - If `nums[j]` is negative, we flip the sign: `productSign *= -1`.
  - If `productSign` is positive (i.e., `1`), it means the subarray `nums[i...j]` has a positive product. We update `maxLength = max(maxLength, j - i + 1)`.
- After iterating through all possible subarrays, return `maxLength`.

## Dynamic Programming with Constant Space
A highly efficient solution can be achieved using a single pass through the array, which is a form of dynamic programming with constant space. The key idea is to keep track of the length of the longest subarray ending at the current position that has a positive product, and similarly, the length of the one with a negative product. Based on the current number (positive, negative, or zero), we can determine the new lengths for these two categories.
**Time:** O(n), where n is the length of the array. We perform a single pass through the array. · **Space:** O(1). We only use a few variables (`maxLength`, `positiveLen`, `negativeLen`, `temp`) regardless of the input size.
**Pros:** Optimal time complexity, solving the problem in a single pass.; Optimal space complexity, using only a constant number of variables.; Handles all edge cases like zeros and sequences of negative numbers gracefully.
**Cons:** The logic, especially the state transitions when a negative number is encountered, can be slightly non-intuitive at first glance.
### Explanation
We iterate through the array, maintaining two counters: `positiveLen` and `negativeLen`. `positiveLen` stores the length of the longest subarray ending at the current index with a positive product, and `negativeLen` does the same for a negative product.

- If we see a `0`, any subarray ending here will have a product of `0`. So, we must start fresh, resetting both `positiveLen` and `negativeLen` to `0`.
- If we see a positive number, it extends both positive and negative product subarrays. We increment `positiveLen`. We also increment `negativeLen` if it's already greater than zero.
- If we see a negative number, it flips the signs. A new positive subarray is formed by adding the negative number to a previous negative subarray. A new negative subarray is formed by adding it to a previous positive subarray. We effectively swap the roles of `positiveLen` and `negativeLen` and increment them. For example, the new `positiveLen` becomes the old `negativeLen + 1`.

At each step of the iteration, the current `positiveLen` represents a valid subarray length, so we continuously update our global `maxLength` with it.

```java
class Solution {
    public int getMaxLen(int[] nums) {
        int maxLength = 0;
        int positiveLen = 0;
        int negativeLen = 0;

        for (int num : nums) {
            if (num == 0) {
                positiveLen = 0;
                negativeLen = 0;
            } else if (num > 0) {
                positiveLen++;
                if (negativeLen > 0) {
                    negativeLen++;
                }
            } else { // num < 0
                int temp = positiveLen;
                // New positive length is from old negative length
                if (negativeLen > 0) {
                    positiveLen = negativeLen + 1;
                } else {
                    positiveLen = 0;
                }
                // New negative length is from old positive length
                negativeLen = temp + 1;
            }
            maxLength = Math.max(maxLength, positiveLen);
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 0`, `positiveLen = 0` (length of subarray ending here with positive product), and `negativeLen = 0` (length of subarray ending here with negative product).
- Iterate through each number `num` in the `nums` array.
- **Case 1: `num == 0`**
  - A zero resets any running product. A subarray containing zero has a product of zero, which is not positive.
  - Reset `positiveLen = 0` and `negativeLen = 0`.
- **Case 2: `num > 0`**
  - Appending a positive number doesn't change the sign of the product.
  - Increment `positiveLen`.
  - If a negative product subarray existed (`negativeLen > 0`), increment `negativeLen` as well.
- **Case 3: `num < 0`**
  - Appending a negative number flips the sign of the product.
  - The new positive-product subarray is formed by appending `num` to the previous negative-product subarray. So, `new_positiveLen = negativeLen + 1` (if `negativeLen > 0`, else 0).
  - The new negative-product subarray is formed by appending `num` to the previous positive-product subarray. So, `new_negativeLen = positiveLen + 1`.
  - We must use the values of `positiveLen` and `negativeLen` from *before* this step, so a temporary variable is needed to hold one of them during the swap.
- After each step, update the overall `maxLength = max(maxLength, positiveLen)`.
- Return `maxLength` after the loop.

# Solutions
### Java

```java
class Solution {
public
  int getMaxLen(int[] nums) {
    int f1 = nums[0] > 0 ? 1 : 0;
    int f2 = nums[0] < 0 ? 1 : 0;
    int res = f1;
    for (int i = 1; i < nums.length; ++i) {
      if (nums[i] > 0) {
        ++f1;
        f2 = f2 > 0 ? f2 + 1 : 0;
      } else if (nums[i] < 0) {
        int pf1 = f1, pf2 = f2;
        f2 = pf1 + 1;
        f1 = pf2 > 0 ? pf2 + 1 : 0;
      } else {
        f1 = 0;
        f2 = 0;
      }
      res = Math.max(res, f1);
    }
    return res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int getMaxLen(vector<int> &nums) {
    int f1 = nums[0] > 0 ? 1 : 0;
    int f2 = nums[0] < 0 ? 1 : 0;
    int res = f1;
    for (int i = 1; i < nums.size(); ++i) {
      if (nums[i] > 0) {
        ++f1;
        f2 = f2 > 0 ? f2 + 1 : 0;
      } else if (nums[i] < 0) {
        int pf1 = f1, pf2 = f2;
        f2 = pf1 + 1;
        f1 = pf2 > 0 ? pf2 + 1 : 0;
      } else {
        f1 = 0;
        f2 = 0;
      }
      res = max(res, f1);
    }
    return res;
  }
};

```

### Python

```python
class Solution:
    def getMaxLen(self, nums: List[int]) -> int: f1 = 1 if nums[0] > 0 else 0 f2 = 1 if nums[0] < 0 else 0 res = f1 for num in nums[1:]: pf1, pf2 = f1, f2 if num > 0: f1 += 1 if f2 > 0: f2 += 1 else: f2 = 0 elif num < 0: pf1, pf2 = f1, f2 f2 = pf1 + 1 if pf2 > 0: f1 = pf2 + 1 else: f1 = 0 else: f1 = 0 f2 = 0 res = max(res, f1) return res

```