Formatted question description: https://leetcode.ca/all/1567.html

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/

// 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/

// 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)

Java

class Solution {
    public int getMaxLen(int[] nums) {
        int maxLen = 0;
        List<Integer> negativeIndices = new ArrayList<Integer>();
        int start = 0;
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            if (nums[i] == 0) {
                int curMaxLen = getMaxLen(negativeIndices, start, i - 1);
                maxLen = Math.max(maxLen, curMaxLen);
                negativeIndices.clear();
                start = i + 1;
            } else {
                if (nums[i] < 0)
                    negativeIndices.add(i);
            }
        }
        int curMaxLen = getMaxLen(negativeIndices, start, length - 1);
        maxLen = Math.max(maxLen, curMaxLen);
        return maxLen;
    }

    public int getMaxLen(List<Integer> negativeIndices, int start, int end) {
        if (start > end)
            return 0;
        int size = negativeIndices.size();
        if (size % 2 == 0)
            return end - start + 1;
        else {
            int firstIndex = negativeIndices.get(0), lastIndex = negativeIndices.get(size - 1);
            return Math.max(lastIndex - start, end - firstIndex);
        }
    }
}

All Problems

All Solutions