Code Implementation

class Solution:
    def getMaxLen(self, nums):
        max_len = 0
        start = 0
        n = len(nums)
        while start < n:
            while start < n and nums[start] == 0:
                start += 1
            end = start
            neg_count = 0
            first_neg = -1
            last_neg = -1
            while end < n and nums[end] != 0:
                if nums[end] < 0:
                    neg_count += 1
                    if first_neg == -1:
                        first_neg = end
                    last_neg = end
                end += 1
            if neg_count % 2 == 0:
                max_len = max(max_len, end - start)
            else:
                if first_neg != -1:
                    max_len = max(max_len, end - first_neg - 1)
                if last_neg != -1:
                    max_len = max(max_len, last_neg - start)
            start = end + 1
        return max_len
      

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int maxLen = 0, n = nums.size();
        int start = 0;
        while (start < n) {
            while (start < n && nums[start] == 0) start++;
            int end = start, negCount = 0, firstNeg = -1, lastNeg = -1;
            while (end < n && nums[end] != 0) {
                if (nums[end] < 0) {
                    negCount++;
                    if (firstNeg == -1) firstNeg = end;
                    lastNeg = end;
                }
                end++;
            }
            if (negCount % 2 == 0) {
                maxLen = max(maxLen, end - start);
            } else {
                if (firstNeg != -1)
                    maxLen = max(maxLen, end - firstNeg - 1);
                if (lastNeg != -1)
                    maxLen = max(maxLen, lastNeg - start);
            }
            start = end + 1;
        }
        return maxLen;
    }
};
      

class Solution {
    public int getMaxLen(int[] nums) {
        int maxLen = 0, n = nums.length;
        int start = 0;
        while (start < n) {
            while (start < n && nums[start] == 0) start++;
            int end = start, negCount = 0, firstNeg = -1, lastNeg = -1;
            while (end < n && nums[end] != 0) {
                if (nums[end] < 0) {
                    negCount++;
                    if (firstNeg == -1) firstNeg = end;
                    lastNeg = end;
                }
                end++;
            }
            if (negCount % 2 == 0) {
                maxLen = Math.max(maxLen, end - start);
            } else {
                if (firstNeg != -1)
                    maxLen = Math.max(maxLen, end - firstNeg - 1);
                if (lastNeg != -1)
                    maxLen = Math.max(maxLen, lastNeg - start);
            }
            start = end + 1;
        }
        return maxLen;
    }
}
      

var getMaxLen = function(nums) {
    let maxLen = 0;
    let n = nums.length;
    let start = 0;
    while (start < n) {
        while (start < n && nums[start] === 0) start++;
        let end = start, negCount = 0, firstNeg = -1, lastNeg = -1;
        while (end < n && nums[end] !== 0) {
            if (nums[end] < 0) {
                negCount++;
                if (firstNeg === -1) firstNeg = end;
                lastNeg = end;
            }
            end++;
        }
        if (negCount % 2 === 0) {
            maxLen = Math.max(maxLen, end - start);
        } else {
            if (firstNeg !== -1)
                maxLen = Math.max(maxLen, end - firstNeg - 1);
            if (lastNeg !== -1)
                maxLen = Math.max(maxLen, lastNeg - start);
        }
        start = end + 1;
    }
    return maxLen;
};
      

Problem Description

Given an array of integers nums, find the length of the longest subarray where the product of all its elements is positive. A subarray is a contiguous part of the array. The product of an empty subarray is not considered. If there is no such subarray, return 0.

Key constraints:

• You cannot skip elements; subarrays must be contiguous.
• Zeros break the product (as the product becomes 0, which is not positive), so subarrays cannot include zeros.
• Negative numbers flip the sign of the product.

Thought Process

The brute-force way would be to check every possible subarray, compute its product, and keep track of the longest one with a positive product. However, this is very inefficient, especially for large arrays.

To optimize, notice that:

• Zeros split the array into independent segments, since the product of any subarray containing zero is zero (not positive).
• Within each segment, the product is positive if there is an even number of negative numbers.
• We only need to track the positions of the first and last negative numbers in each segment to determine the maximal positive product subarray.

Solution Approach

We solve the problem by breaking it into the following steps:

1. Segment the array by zeros:
   • Iterate through nums, and for each segment (between zeros), process it separately.
2. Count negatives and track their positions:
   • For each segment, count how many negative numbers there are.
   • Record the index of the first and last negative number in the segment.
3. Determine the maximal subarray with positive product:
   • If the number of negatives is even, the whole segment's product is positive.
   • If odd, the maximal positive product subarray is either after the first negative or before the last negative (excluding one negative to make the count even).
4. Update the maximum length:
   • For each segment, update the answer with the maximum length found.

Example Walkthrough

Let's use the input nums = [1, -2, -3, 4].

• There are no zeros, so the entire array is one segment.
• Count negatives: -2 and -3 are negative, so there are 2 negatives (even).
• Since the count is even, the product of the whole segment is positive.
• The maximal length is 4 (the whole array).

Now, with nums = [0, 1, -2, -3, -4, 0, 5, 6, -7]:

• Segment 1: [1, -2, -3, -4]
  • Negatives: -2, -3, -4 (3 negatives, odd)
  • First negative at index 1, last at index 3 (relative to segment)
  • Max positive product subarray: Exclude first negative (from index 2 to 3: [-3, -4], length 2) or exclude last negative (from index 0 to 2: [1, -2, -3], length 3)
  • So, maximal length is 3
• Segment 2: [5, 6, -7]
  • Negatives: -7 (1 negative, odd)
  • First and last negative at index 2
  • Max positive product subarray: Exclude first/last negative (from index 0 to 1: [5,6], length 2)
• Overall maximal length is 3

Time and Space Complexity

• Brute-force approach: O(N²) time, where N is the length of nums, because it checks all subarrays.
• Optimized approach: O(N) time and O(1) space.
  • We only make one pass through the array, and use a constant number of variables to track counts and indices.

Summary

The key insight is to break the array into segments separated by zeros and analyze each segment for the parity of negative numbers. By tracking the first and last negative, we can efficiently find the maximal positive product subarray in each segment. This approach avoids unnecessary computation and leverages properties of multiplication and sign, making the solution both elegant and efficient.