Maximum segment length such that product is positive
Filed under Arcesium
Free read 2 of 3Confirm how zeros are handled (they yield a product of 0, which is not positive, thus splitting valid segments).
The question
Given an array of integers, find the maximum length of a contiguous subarray where the product of all elements is positive.
Constraints
- 1 <= array length <= 10^5
- -10^9 <= array[i] <= 10^9
Examples
- Input
- nums = [1, -2, -3, 4]
- Output
- 4
- Why
- The product of the entire array is 1 * (-2) * (-3) * 4 = 24, which is positive. Length is 4.
Approach
Confirm how zeros are handled (they yield a product of 0, which is not positive, thus splitting valid segments).
Check every possible subarray and compute its product, resulting in O(n^2) or O(n^3) time.
Track the length of positive and negative product subarrays ending at the current index dynamically in a single pass.
Array contains all negative numbers or multiple zeros.
Solution
O(n) time, O(1) space
class Solution:
def getMaxLen(self, nums: list[int]) -> int:
pos_len = neg_len = max_len = 0
for num in nums:
if num > 0:
pos_len += 1
neg_len = neg_len + 1 if neg_len > 0 else 0
elif num < 0:
temp = pos_len
pos_len = neg_len + 1 if neg_len > 0 else 0
neg_len = temp + 1
else:
pos_len = neg_len = 0
max_len = max(max_len, pos_len)
return max_len
Tips
- What they are testing: Test arrays with zeros, all negative numbers, and alternating signs.
- Common mistake: Ignoring zeros which reset the subarray product window.
Related Arcesium questions
Collected from public candidate posts and coding forums. Updated Nov 2026.