[LeetCode] 1567. Maximum Length of Subarray With Positive Product

[plh97]

一道大数题目. 找出最长的数组区间, 这个区间内的数相乘为正数

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

大数的一般处理思路就是分割数组, 将大的问题化成一个个小问题再一一解决.

1. 以0位分割点, 分割生成不同的子数组,

2. 分别计算子数组中的负数个数

3. 偶数个数的负数, 直接输出数组长度,

4. 奇数个数的负数, 找出这个数组中左右分别第一个负数, 输出长度 减去这个index.

5. 将这个结果收集起来, 拿到最大数.

答案

/**
 * @param {number[]} nums
 * @return {number}
 */
var getMaxLen = function(nums) {
    // length from high to low
    let max = 0
    let sz = nums.length
    let arrSplit0 = []
    let temp = []
    nums.forEach(e=>{
        if (e==0) {
            arrSplit0.push(temp)
            temp = []
        }else{
            temp.push(e)
        }
    })
    arrSplit0.push(temp)
    arrSplit0 = arrSplit0.map(arr=>{
        let neg = 0
        arr.forEach(e=>{
            if (e<0) {
                neg++
            }
        })
        if (neg%2==0) {
            return arr.length
        }else{
            for(let i=0,j=arr.length-1;i<j;i++,j--) {
                if(arr[i]<0 || arr[j]<0) {
                    return arr.length-i-1
                }
            }
            return 0
        }
    })
    return Math.max(...arrSplit0)
};