1567. Maximum Length of Subarray With Positive Product

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

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].

Example 4:

Input: nums = [-1,2]
Output: 1

Example 5:

Input: nums = [1,2,3,5,-6,4,0,10]
Output: 4

 

Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

Related Topics:
Greedy

Solution 1.

• We shouldn't include 0 in the subarray. So we just handle each of the subarrays surrounded by 0s.
• If there are even number of negative numbers in the subarray, the entire subarray has a positive product.
• If there are odd number of negative numbers in the subarray, we have two candidates:
  1. From the first element of the subarray to the element before the last negative element
  2. From the next element of first negative element to the last element of the subarray.

// OJ: https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int getMaxLen(vector<int>& A) {
        int j = 0, N = A.size(), ans = 0;
        while (j < N) {
            int i = j, cnt = 0, first = -1, last;
            for (; j < N && A[j] != 0; ++j) {
                cnt += A[j] < 0;
                if (A[j] < 0) {
                    if (first == -1) first = j;
                    last = j;
                }
            }
            if (cnt % 2) ans = max({ ans, j - first - 1, last - i });
            else ans = max(ans, j - i);
            while (j < N && A[j] == 0) ++j;
        }
        return ans;
    }
};

Or

// OJ: https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int getMaxLen(vector<int>& A) {
        int N = A.size(), i = 0, ans = 0;
        while (i < N) {
            while (i < N && A[i] == 0) ++i;
            if (i == N) break;
            int start = i, cnt = 0, first = -1;
            for (; i < N && A[i] != 0; ++i) {
                cnt += A[i] < 0;
                if (A[i] < 0 && first == -1) first = i; 
                if (cnt % 2 == 0) ans = max(ans, i - start + 1);
                else ans = max(ans, i - first);
            }
        }
        return ans;
    }
};

Note

Similar problem: 152. Maximum Product Subarray (Medium)