1567. Maximum Length of Subarray With Positive Product (M)

Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

Return the maximum length of a subarray with positive product.

Example 1:

Input: nums = [1,-2,-3,4]
Output: 4
Explanation: The array nums already has a positive product of 24.

Example 2:

Input: nums = [0,1,-2,-3,-4]
Output: 3
Explanation: The longest subarray with positive product is [1,-2,-3] which has a product of 6.
Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.

Example 3:

Input: nums = [-1,-2,-3,0,1]
Output: 2
Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].

Constraints:

• 1 <= nums.length <= 105

• -109 <= nums[i] <= 109

Solution:

Version 1: DP

• p[i] := max length of positive products ends with arr[i]

• n[i] := max length of negtive products ends with arr[i]

if arr[i] > 0: p[i] = p[i – 1] + 1, n[i] = n[i] + 1 if n[i] else 0 if arr[i] < 0: p[i] = n[i – 1] + 1 if n[i – 1] else 0, n[i] = p[i – 1] + 1 if arr[i] == 0: p[i] = n[i] = 0 ans = max(p[i])

Time complexity: O(n) Space complexity: O(n) -> O(1)

class Solution {
    public int getMaxLen(int[] nums) {
        
        int l = nums.length;
        int[] p = new int[l];
        int[] n = new int[l];
        
        if(nums[0] >0)
        {
            p[0] = 1;
            n[0] = 0;
        }
        else if(nums[0] < 0)
        {
            p[0] = 0;
            n[0] = 1;
        }
        else
        {
            p[0] = n[0] = 0;
        }
        
        int result = p[0];
        for(int i = 1; i< l ;i++)
        {
            if(nums[i] > 0)
            {
                p[i] = p[i-1]+1;
                if(n[i-1] == 0)
                {
                    n[i] = n[i-1];
                }else
                {
                    n[i] = n[i-1]+1;
                }
            }
            else if(nums[i] < 0)
            {
                if(n[i-1] == 0)
                {
                    p[i] = n[i-1];
                }
                else
                {
                    p[i] = n[i-1] +1;
                }
                
                n[i] = p[i-1] +1;
            }
            else
            {
                p[i] = n[i] = 0;
            }
            
            result = Math.max(result, p[i]);
        }
        return result;
        
    }
}

Version 2: Sliding Window

https://www.gyanblog.com/coding-interview/leetcode-solution-max-length-positive-product/

Note: We don’t have to include value-0 in our result. This adds to additional complexity to problem.

Lets think of sliding window kind of solution where we keep track of some indexes and calculate the result.

Few things to keep in mind:

• You can not leave a negative number as it is. As multiplication of two negative numbers is positive

• You don’t need to actually multiply numbers. The question is about maximum subarray length which multiplies to a positive result.

• You just need to keep a track of how many numbers multiplies to a positive result.

• If your negative counts becomes odd, you would want to remove a negative number from your range.