Skip to content

1567. Maximum Length of Subarray With Positive Product

Description

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

Solutions

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        f1 = 1 if nums[0] > 0 else 0
        f2 = 1 if nums[0] < 0 else 0
        res = f1
        for num in nums[1:]:
            pf1, pf2 = f1, f2
            if num > 0:
                f1 += 1
                if f2 > 0:
                    f2 += 1
                else:
                    f2 = 0
            elif num < 0:
                pf1, pf2 = f1, f2
                f2 = pf1 + 1
                if pf2 > 0:
                    f1 = pf2 + 1
                else:
                    f1 = 0
            else:
                f1 = 0
                f2 = 0
            res = max(res, f1)
        return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int getMaxLen(int[] nums) {
        int f1 = nums[0] > 0 ? 1 : 0;
        int f2 = nums[0] < 0 ? 1 : 0;
        int res = f1;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] > 0) {
                ++f1;
                f2 = f2 > 0 ? f2 + 1 : 0;
            } else if (nums[i] < 0) {
                int pf1 = f1, pf2 = f2;
                f2 = pf1 + 1;
                f1 = pf2 > 0 ? pf2 + 1 : 0;
            } else {
                f1 = 0;
                f2 = 0;
            }
            res = Math.max(res, f1);
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int f1 = nums[0] > 0 ? 1 : 0;
        int f2 = nums[0] < 0 ? 1 : 0;
        int res = f1;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] > 0) {
                ++f1;
                f2 = f2 > 0 ? f2 + 1 : 0;
            } else if (nums[i] < 0) {
                int pf1 = f1, pf2 = f2;
                f2 = pf1 + 1;
                f1 = pf2 > 0 ? pf2 + 1 : 0;
            } else {
                f1 = 0;
                f2 = 0;
            }
            res = max(res, f1);
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func getMaxLen(nums []int) int {
    f1, f2 := 0, 0
    if nums[0] > 0 {
        f1 = 1
    }
    if nums[0] < 0 {
        f2 = 1
    }
    res := f1
    for i := 1; i < len(nums); i++ {
        if nums[i] > 0 {
            f1++
            if f2 > 0 {
                f2++
            } else {
                f2 = 0
            }
        } else if nums[i] < 0 {
            pf1, pf2 := f1, f2
            f2 = pf1 + 1
            if pf2 > 0 {
                f1 = pf2 + 1
            } else {
                f1 = 0
            }
        } else {
            f1, f2 = 0, 0
        }
        res = max(res, f1)
    }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function getMaxLen(nums: number[]): number {
    // 连续正数计数n1, 连续负数计数n2
    let n1 = nums[0] > 0 ? 1 : 0,
        n2 = nums[0] < 0 ? 1 : 0;
    let ans = n1;
    for (let i = 1; i < nums.length; ++i) {
        let cur = nums[i];
        if (cur == 0) {
            (n1 = 0), (n2 = 0);
        } else if (cur > 0) {
            ++n1;
            n2 = n2 > 0 ? n2 + 1 : 0;
        } else {
            let t1 = n1,
                t2 = n2;
            n1 = t2 > 0 ? t2 + 1 : 0;
            n2 = t1 + 1;
        }
        ans = Math.max(ans, n1);
    }
    return ans;
}

Comments