Maximum Length of Subarray With Positive Product

Medium
1350.

Maximum Length of Subarray With Positive Product

Maximum Length of Subarray With Positive Product is a medium coding problem on arrays, dynamic programming and greedy, asked in Amazon, Microsoft and Arcesium interviews.

Given an integer array nums, return the length of the longest contiguous subarray whose product of all elements is strictly positive.

A subarray is a run of consecutive elements. If no subarray has a positive product (for example, every element is zero or negative and isolated by zeros), return 0.

You only need the sign of the product — the values themselves can be large.

Example 1

Input
nums = [2,-5,-1,3]
Output
4
Explanation
The two negatives cancel, so the whole array has product 30.

Example 2

Input
nums = [0,4,-1,-2,-6]
Output
3
Explanation
`[4,-1,-2]` has product 8. Any window containing all three negatives is negative, and the zero cannot be included.

Example 3

Input
nums = [-3,-7,-2,0,5]
Output
2
Explanation
`[-3,-7]` or `[-7,-2]`; the run of three negatives is negative.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var getMaxLen = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Length of Subarray With Positive Product — Solution

Maximum Length of Subarray With Positive Product solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Length of Subarray With Positive Product is a medium coding problem on arrays, dynamic programming and greedy, asked in Amazon, Microsoft and Arcesium interviews.

Problem statement

Given an integer array nums, return the length of the longest contiguous subarray whose product of all elements is strictly positive.

A subarray is a run of consecutive elements. If no subarray has a positive product (for example, every element is zero or negative and isolated by zeros), return 0.

You only need the sign of the product — the values themselves can be large.

Example 1

Input: nums = [2,-5,-1,3]
Output: 4
Explanation: The two negatives cancel, so the whole array has product 30.

Example 2

Input: nums = [0,4,-1,-2,-6]
Output: 3
Explanation: `[4,-1,-2]` has product 8. Any window containing all three negatives is negative, and the zero cannot be included.

Example 3

Input: nums = [-3,-7,-2,0,5]
Output: 2
Explanation: `[-3,-7]` or `[-7,-2]`; the run of three negatives is negative.

Constraints

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

Hints for Maximum Length of Subarray With Positive Product

  1. Hint 1

    A zero kills every subarray that contains it, so the array splits into independent zero-free segments.

  2. Hint 2

    Inside a zero-free segment the sign of a product depends only on how many negatives it holds — an even count means positive.

  3. Hint 3

    Scan once, tracking two lengths that end at the current index: the longest with a positive product and the longest with a negative product. A negative number swaps them (each extended by one).

How to solve Maximum Length of Subarray With Positive Product

Track, for subarrays ending at the current index, the longest one with a positive product (pos) and the longest with a negative product (neg). Each new element updates both in O(1).

Approach

  1. Start with pos = neg = 0 and best = 0.
  2. For a positive element: pos = pos + 1; neg = neg + 1 if neg > 0, otherwise it stays 0 (a positive number alone cannot start a negative product).
  3. For a negative element: the new pos is neg + 1 if neg > 0 (else 0), and the new neg is pos + 1 — compute both from the old values.
  4. For zero: reset pos = neg = 0.
  5. After each element, best = max(best, pos).

Why it works

Every subarray ending at index i is an extension of a subarray ending at i - 1 (or the element alone). Multiplying by a positive keeps signs, by a negative flips them, and a zero makes everything 0. So the longest positive and longest negative runs ending at i are determined by the two values at i - 1, and the answer is the best pos over all end positions.

Complexity

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

Pitfalls

  • Never multiply the actual values — with up to 10^5 factors of size 10^9 the product overflows every integer type. Only signs matter.
  • On a negative element, update pos and neg simultaneously from the previous values (use a temporary).
  • neg + 1 is only valid when a negative run exists (neg > 0); otherwise the extension does not exist and the value must be 0.

Reference solution

Python

from typing import List

def getMaxLen(nums: List[int]) -> int:
    pos = 0
    neg = 0
    best = 0
    for v in nums:
        if v > 0:
            pos += 1
            neg = neg + 1 if neg > 0 else 0
        elif v < 0:
            new_pos = neg + 1 if neg > 0 else 0
            neg = pos + 1
            pos = new_pos
        else:
            pos = 0
            neg = 0
        best = max(best, pos)
    return best

Java

public static int getMaxLen(int[] nums) {
    int pos = 0, neg = 0, best = 0;
    for (int v : nums) {
        if (v > 0) {
            pos = pos + 1;
            neg = neg > 0 ? neg + 1 : 0;
        } else if (v < 0) {
            int np = neg > 0 ? neg + 1 : 0;
            neg = pos + 1;
            pos = np;
        } else {
            pos = 0;
            neg = 0;
        }
        best = Math.max(best, pos);
    }
    return best;
}

C++

int getMaxLen(vector<int>& nums) {
    int pos = 0, neg = 0, best = 0;
    for (int v : nums) {
        if (v > 0) {
            pos = pos + 1;
            neg = neg > 0 ? neg + 1 : 0;
        } else if (v < 0) {
            int np = neg > 0 ? neg + 1 : 0;
            neg = pos + 1;
            pos = np;
        } else {
            pos = 0;
            neg = 0;
        }
        best = max(best, pos);
    }
    return best;
}

JavaScript

var getMaxLen = function(nums) {
    var pos = 0, neg = 0, best = 0;
    for (var i = 0; i < nums.length; i++) {
        var v = nums[i];
        if (v > 0) {
            pos = pos + 1;
            neg = neg > 0 ? neg + 1 : 0;
        } else if (v < 0) {
            var np = neg > 0 ? neg + 1 : 0;
            neg = pos + 1;
            pos = np;
        } else {
            pos = 0;
            neg = 0;
        }
        if (pos > best) best = pos;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming