Maximum Length of Subarray With Positive Product: Tracking Sign Flips

June 1, 20265 min read

leetcodeproblemmediumarraysdynamic-programminggreedy

Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.

This is LeetCode 1567: Maximum Length of Subarray With Positive Product. A product is positive when the number of negative values in the subarray is even (including zero negatives). Zeros break the chain entirely because any product involving zero is zero, not positive.

nums = [1, -2, -3, 4]. Green = positive, red = negative. The entire array has a positive product (1 * -2 * -3 * 4 = 24), so the answer is 4.

Why this problem is trickier than it looks

Your first instinct might be to just count negatives and figure out the longest window with an even count. But zeros complicate things: they split the array into independent segments. And within each segment you need to figure out which negatives to include or exclude.

A cleaner approach is to think about it as a DP problem where you track two values at every position:

pos: the length of the longest subarray ending at this index whose product is positive
neg: the length of the longest subarray ending at this index whose product is negative

The key insight is that these two counters interact with each new element based on its sign. A positive number extends both. A negative number swaps them (positive becomes negative, negative becomes positive). A zero resets both to 0.

Think of pos and neg as two parallel trackers. When you hit a negative number, the longest positive-product subarray flips into the longest negative-product subarray and vice versa. This swap is the entire trick.

The solution

def getMaxLen(nums: list[int]) -> int:
    pos = 0
    neg = 0
    result = 0

    for num in nums:
        if num > 0:
            pos += 1
            neg = neg + 1 if neg > 0 else 0
        elif num < 0:
            pos, neg = neg + 1 if neg > 0 else 0, pos + 1
        else:
            pos = 0
            neg = 0

        result = max(result, pos)

    return result

Practice this problem with spaced repetition

How it works

Walk through the logic for each case:

When num is positive: A positive number does not change the sign of any product. If you already have a positive-product subarray of length pos, appending a positive number keeps it positive, so pos grows by 1. If you have a negative-product subarray of length neg, appending a positive number keeps it negative, so neg also grows by 1. But if neg is 0 (there is no negative-product subarray ending here), it stays 0 because you cannot create a negative product by appending a positive number to nothing.

When num is negative: This is where the swap happens. A negative number flips the sign of any product. So the new positive-product length comes from the old negative-product length plus 1 (if a negative-product subarray existed). The new negative-product length comes from the old positive-product length plus 1 (because appending a negative to a positive product makes it negative). Note the simultaneous assignment: pos, neg = ... ensures you use the old values for both calculations.

When num is zero: Zero kills everything. Any subarray including a zero has product zero, which is neither positive nor negative. Reset both counters to 0. The next element starts fresh.

After processing each element, update result with the current pos.

Visual walkthrough

Let's trace through nums = [1, -2, -3, 4] step by step. Watch how pos and neg update at each element and how the two negatives eventually cancel each other out.

Step 1: i = 0, nums[0] = 1 (positive)

Positive number: pos increments to 1. neg stays 0 because there is no negative-product subarray yet. result = 1.

Step 2: i = 1, nums[1] = -2 (negative)

Negative flips the roles. New pos = neg + 1 if neg > 0, else 0. Since neg was 0, pos becomes 0. New neg = old pos + 1 = 2. result stays 1.

Step 3: i = 2, nums[2] = -3 (negative)

Another negative flips again. New pos = neg + 1 = 3 (the two negatives cancel out). New neg = old pos + 1 = 0 + 1 = 1. result = 3.

Step 4: i = 3, nums[3] = 4 (positive)

Positive extends both. pos = 3 + 1 = 4. neg = 1 + 1 = 2 (there is still a negative-product subarray). result = 4. Done!

Notice how at step 2, hitting -2 sets pos to 0 because there was no negative-product subarray to flip. But neg becomes 2 because the subarray [1, -2] has a negative product. Then at step 3, another negative flips that neg of 2 back into a pos of 3: the subarray [1, -2, -3] now has a positive product (two negatives cancel out).

Build your pattern library with CodeBricks

Complexity analysis

Approach	Time	Space
Brute force (check all subarrays)	O(n^2)	O(1)
Sign-tracking DP	O(n)	O(1)

The optimal solution visits each element exactly once and uses only three variables (pos, neg, result). You cannot do better than O(n) since you need to look at every element at least once.

Building blocks

This problem is built on two reusable patterns:

1. Sign-tracking DP. Instead of tracking actual product values (which can overflow or get complicated), you track the length of subarrays with specific sign properties. This is a clever reduction: you do not care about the magnitude of the product, only whether it is positive, negative, or zero. The same idea applies to any problem where you need to track a binary or ternary property across a contiguous subarray.

2. Subarray state machine. At each position you maintain a small state (pos and neg) that fully describes what you need to know about all subarrays ending here. The transitions depend on the current element's sign. This is the same structure as Maximum Subarray (Kadane's algorithm) and Maximum Product Subarray, just with a different set of state variables and transition rules.

Edge cases

All positive like [2, 3, 5, 1]: every element extends pos. Answer equals the array length.
Single negative like [3, -1, 2]: the product 3 * (-1) * 2 = -6 is negative, so the full array does not qualify. The longest positive-product subarrays are [3] and [2], each length 1. Answer is 1.
Two negatives like [-1, -2, 3]: the two negatives cancel. Product of all three is 6 (positive), so the answer is 3.
Contains zero like [1, 0, -1, 2]: the zero splits into [1] and [-1, 2]. In [1], pos = 1. After the zero, reset. In [-1, 2], [-1] has negative product, [-1, 2] has negative product, so pos = 0 for that segment. The best is 1.
All zeros like [0, 0, 0]: every element resets. Answer is 0 because no subarray has a positive product.
Single element [5] or [-3]: if positive, answer is 1. If negative, answer is 0.

From understanding to recall

You now understand the two-counter trick: track pos and neg, swap on negatives, reset on zeros. The logic is clean and the code is short. But will you remember the exact transition rules in a week? Will you remember that neg only increments from neg + 1 when neg > 0, not when it is zero?

Spaced repetition is how you move from "I understand this" to "I can write this from memory." You revisit the sign-tracking DP pattern at increasing intervals, writing the solution fresh each time. After a few reps, the three cases (positive, negative, zero) and their transitions become automatic.

Sign-tracking DP and subarray state machines are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Maximum Subarray - Kadane's algorithm for the sum version. Same single-pass DP skeleton, but you only need one tracker because sums do not flip signs.
Maximum Product Subarray - Track both min and max products. Similar sign-awareness, but tracking actual values instead of lengths.
Best Time to Buy and Sell Stock - Another single-pass DP where you track a running minimum and update the best result as you go.

Try CodeBricks free