To solve this problem, we need to find the maximum length of a contiguous subarray where the product of all elements is positive. The key insight is to consider segments of the array separated by zeros (since any subarray containing a zero will have a product of zero, which is not positive) and analyze each segment for the longest valid subarray.

Approach

1. Segmentation by Zeros: Split the array into segments separated by zeros. Each segment is a contiguous subarray with no zeros.
2. Analyze Each Segment:
   • Count Negative Numbers: For each segment, count the number of negative elements.
   • Even Number of Negatives: If the count of negatives is even, the entire segment is valid (product is positive).
   • Odd Number of Negatives: If the count is odd, we need to exclude either the first negative element or the last negative element to make the product positive. The maximum length of the valid subarray in this case is the maximum of:
     • The length from the start of the segment to just before the last negative element.
     • The length from just after the first negative element to the end of the segment.
3. Compute Maximum Length: Track the maximum length of valid subarrays across all segments.

Solution Code

def maxLengthPositiveProduct(nums):
    max_len = 0
    start = 0
    n = len(nums)

    for i in range(n + 1):
        if i == n or nums[i] == 0:
            # Process the segment from start to i-1
            if start < i:
                cnt_neg = 0
                first_neg = -1
                last_neg = -1
                for j in range(start, i):
                    if nums[j] < 0:
                        cnt_neg += 1
                        if first_neg == -1:
                            first_neg = j
                        last_neg = j
                if cnt_neg % 2 == 0:
                    candidate = i - start
                else:
                    # Calculate options
                    option1 = last_neg - start  # up to last_neg -1
                    option2 = i - (first_neg + 1)  # from first_neg +1 to end
                    candidate = max(option1, option2)
                if candidate > max_len:
                    max_len = candidate
            # Reset start to next position after zero
            start = i + 1
    return max_len

Explanation

• Segmentation: The array is split into non-zero segments by checking for zeros. Each segment is processed independently.
• Negative Count: For each segment, we count the number of negatives and find the positions of the first and last negative elements.
• Valid Subarray Calculation:
  • If there are even negatives, the entire segment is valid.
  • If there are odd negatives, we exclude either the first or last negative to get the longest valid subarray.
• Efficiency: The algorithm runs in O(n) time (each element is processed once) and uses O(1) space (no extra arrays, just variables to track segment details). This makes it suitable for large input sizes up to 100,000 elements.

This approach efficiently finds the maximum length of a subarray with a positive product by leveraging the properties of product signs and segment analysis. It handles all edge cases, including zeros and all-negative segments, correctly.

作者声明:本文包含人工智能生成内容。