Solution Explanation for Maximum Length of Subarray With Positive Product

This problem asks to find the maximum length of a subarray within a given array where the product of all elements in that subarray is positive. The solution utilizes dynamic programming for an efficient approach.

Approach: Dynamic Programming

The core idea is to track two pieces of information for each index i in the input array nums:

1. f[i]: The maximum length of a subarray ending at index i with a positive product.
2. g[i]: The maximum length of a subarray ending at index i with a negative product.

We iterate through the array. For each number nums[i]:

• If nums[i] > 0: A positive number extends a positive product. Thus, f[i] = f[i-1] + 1. A negative product can also be extended, but only if a negative product existed before (g[i-1] > 0), so g[i] = g[i-1] + 1. Otherwise, g[i] = 0.
• If nums[i] < 0: A negative number flips the sign of the product. A positive product becomes a negative one, and vice-versa. So, f[i] = g[i-1] + 1 (if g[i-1] exists), and g[i] = f[i-1] + 1. If no previous subarray with a positive product exists, f[i] will be 0.
• If nums[i] == 0: A zero resets everything. Both f[i] and g[i] become 0.

The maximum length of a subarray with a positive product is simply the maximum value encountered in the f array during the iteration.

Space Optimization

The dynamic programming approach can be further optimized. We only need to store the values from the previous index. Thus, we can replace the arrays f and g with two variables to track f[i-1] and g[i-1] reducing the space complexity to O(1).

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
• Space Complexity: O(1) (Optimized version). The space used is constant regardless of the input size. The original DP approach uses O(n) space for the f and g arrays.

Code Implementation (Optimized - O(1) space)

The following code snippets demonstrate the space-optimized solution in several programming languages.

Python:

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        pos = neg = ans = 0
        if nums[0] > 0:
            pos = 1
        elif nums[0] < 0:
            neg = 1
        ans = pos
        for i in range(1, n):
            if nums[i] > 0:
                pos += 1
                neg = neg > 0 and neg + 1 or 0
            elif nums[i] < 0:
                pos, neg = neg > 0 and neg + 1 or 0, pos + 1
            else:
                pos = neg = 0
            ans = max(ans, pos)
        return ans

Java:

class Solution {
    public int getMaxLen(int[] nums) {
        int pos = 0, neg = 0, ans = 0;
        if (nums[0] > 0) pos = 1;
        else if (nums[0] < 0) neg = 1;
        ans = pos;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] > 0) {
                pos++;
                neg = neg > 0 ? neg + 1 : 0;
            } else if (nums[i] < 0) {
                int temp = pos;
                pos = neg > 0 ? neg + 1 : 0;
                neg = temp + 1;
            } else {
                pos = neg = 0;
            }
            ans = Math.max(ans, pos);
        }
        return ans;
    }
}

C++:

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int pos = 0, neg = 0, ans = 0;
        if (nums[0] > 0) pos = 1;
        else if (nums[0] < 0) neg = 1;
        ans = pos;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] > 0) {
                pos++;
                neg = neg > 0 ? neg + 1 : 0;
            } else if (nums[i] < 0) {
                int temp = pos;
                pos = neg > 0 ? neg + 1 : 0;
                neg = temp + 1;
            } else {
                pos = neg = 0;
            }
            ans = max(ans, pos);
        }
        return ans;
    }
};

Similar implementations can be done in other languages following the same logic. The space-optimized version is generally preferred due to its better space efficiency, especially for very large input arrays.