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.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Greedy
- Asked at: Amazon, Microsoft, Arcesium
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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
Hint 1
A zero kills every subarray that contains it, so the array splits into independent zero-free segments.
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.
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
- Start with
pos = neg = 0andbest = 0. - For a positive element:
pos = pos + 1;neg = neg + 1ifneg > 0, otherwise it stays 0 (a positive number alone cannot start a negative product). - For a negative element: the new
posisneg + 1ifneg > 0(else 0), and the newnegispos + 1— compute both from the old values. - For zero: reset
pos = neg = 0. - 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
posandnegsimultaneously from the previous values (use a temporary). neg + 1is 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 bestJava
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