Maximum Length of Subarray With Positive Product

medium array dp greedy

Problem

Return the maximum length of a contiguous subarray whose product is strictly positive.

Inputnums = [0,1,-2,-3,-4]

Output3

Subarray [1,-2,-3] has product 6 > 0; length 3.

nums

def get_max_len(nums):
    pos = neg = best = 0
    for x in nums:
        if x == 0: pos = neg = 0
        elif x > 0: pos += 1; neg = neg + 1 if neg else 0
        else:
            new_pos = neg + 1 if neg else 0
            new_neg = pos + 1
            pos, neg = new_pos, new_neg
        best = max(best, pos)
    return best

function getMaxLen(nums) {
  let pos = 0, neg = 0, best = 0;
  for (const x of nums) {
    if (x === 0) { pos = 0; neg = 0; }
    else if (x > 0) { pos++; neg = neg ? neg + 1 : 0; }
    else { const p = neg ? neg + 1 : 0, n = pos + 1; pos = p; neg = n; }
    if (pos > best) best = pos;
  }
  return best;
}

class Solution {
    public int getMaxLen(int[] nums) {
        int pos = 0, neg = 0, best = 0;
        for (int x : nums) {
            if (x == 0) { pos = 0; neg = 0; }
            else if (x > 0) { pos++; neg = neg > 0 ? neg + 1 : 0; }
            else { int p = neg > 0 ? neg + 1 : 0, n = pos + 1; pos = p; neg = n; }
            best = Math.max(best, pos);
        }
        return best;
    }
}

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

Explanation

A product is positive when the count of negative numbers in it is even. So as we sweep the array, we keep two running streak lengths: pos = longest run ending here with a positive product, and neg = longest run ending here with a negative product.

When the current number x is positive, it doesn't change any sign, so both streaks just grow by one: pos++, and neg grows only if a negative run already existed.

When x is negative, it flips the signs. A run that was negative becomes positive and a run that was positive becomes negative, so we swap: the new pos comes from the old neg (plus this element), and the new neg comes from the old pos + 1.

When x is zero, no product through it can be nonzero, so both streaks reset to 0. After each step we update best with the current pos.

Example: for [0,1,-2,-3,-4], the two negatives in [1,-2,-3] cancel to a positive product, letting pos reach 3, the answer.

Time: O(n) Space: O(1)