Naive Approach

A brute-force solution would involve iterating through all possible subarrays and checking if the product of each subarray is positive. We would keep track of the maximum length of such a subarray.

def max_len_brute_force(nums):
    max_length = 0
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            product = 1
            for k in range(i, j + 1):
                product *= nums[k]
            if product > 0:
                max_length = max(max_length, j - i + 1)
    return max_length

Time Complexity: O(n^3), where n is the length of the input array nums. This is because we have nested loops to iterate through all possible subarrays, and another inner loop to calculate the product of each subarray.

Space Complexity: O(1), as we are only using a constant amount of extra space.

Optimal Approach

A more efficient solution involves using dynamic programming. We can keep track of the maximum length of positive and negative product subarrays ending at each index. Let pos[i] be the maximum length of a positive product subarray ending at index i, and neg[i] be the maximum length of a negative product subarray ending at index i.

1. If nums[i] > 0, then pos[i] = pos[i-1] + 1 and neg[i] = neg[i-1] + 1 if neg[i-1] > 0, otherwise neg[i] = 0.
2. If nums[i] < 0, then pos[i] = neg[i-1] + 1 if neg[i-1] > 0, otherwise pos[i] = 0, and neg[i] = pos[i-1] + 1.
3. If nums[i] == 0, then pos[i] = 0 and neg[i] = 0.

We can optimize space by just using two variables to store the current positive and negative lengths instead of arrays.

def get_max_len(nums):
    pos = 0
    neg = 0
    max_length = 0

    for num in nums:
        if num > 0:
            pos += 1
            neg = neg + 1 if neg > 0 else 0
        elif num < 0:
            new_pos = neg + 1 if neg > 0 else 0
            new_neg = pos + 1
            pos = new_pos
            neg = new_neg
        else:
            pos = 0
            neg = 0
        max_length = max(max_length, pos)

    return max_length

Time Complexity: O(n), where n is the length of the input array nums. We iterate through the array only once.

Space Complexity: O(1), as we are only using a constant amount of extra space.

Edge Cases

• Empty array: Should return 0.
• Array with all zeros: Should return 0.
• Array with a mix of positive, negative, and zero values.
• Array with all positive values: Should return the length of the array.
• Array with all negative values: Should return 0 if the length is even, and 1 if the length is odd.