Problem

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.

Examples

Example 1

1
2
3

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

Example 2

1
2
3
4

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

1
2
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 <= 10^5
  • -109 <= nums[i] <= 10^9

Solution

Method 1 – Dynamic Programming (Sign Tracking)

Intuition

To find the maximum length of a subarray with a positive product, we can track for each position the length of the longest subarray ending there with a positive or negative product. When we see a zero, we reset. When we see a negative, the roles of positive and negative lengths swap.

Approach

  1. Initialize two variables: pos (length of subarray ending at current index with positive product), neg (with negative product), both set to 0.
  2. Iterate through nums:
    • If nums[i] == 0: reset pos and neg to 0.
    • If nums[i] > 0: pos += 1, neg = neg > 0 ? neg + 1 : 0.
    • If nums[i] < 0: swap pos and neg, then pos = neg > 0 ? neg + 1 : 0, neg = old_pos > 0 ? old_pos + 1 : 1.
  3. Track the maximum value of pos during the iteration.
  4. Return the maximum value found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int pos = 0, neg = 0, ans = 0;
        for (int x : nums) {
            if (x == 0) pos = neg = 0;
            else if (x > 0) {
                pos += 1;
                neg = neg > 0 ? neg + 1 : 0;
            } else {
                int tmp = pos;
                pos = neg > 0 ? neg + 1 : 0;
                neg = tmp > 0 ? tmp + 1 : 1;
            }
            ans = max(ans, pos);
        }
        return ans;
    }
};
 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

func getMaxLen(nums []int) int {
    pos, neg, ans := 0, 0, 0
    for _, x := range nums {
        if x == 0 {
            pos, neg = 0, 0
        } else if x > 0 {
            pos++
            if neg > 0 {
                neg++
            } else {
                neg = 0
            }
        } else {
            tmp := pos
            if neg > 0 {
                pos = neg + 1
            } else {
                pos = 0
            }
            if tmp > 0 {
                neg = tmp + 1
            } else {
                neg = 1
            }
        }
        if pos > ans {
            ans = pos
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int getMaxLen(int[] nums) {
        int pos = 0, neg = 0, ans = 0;
        for (int x : nums) {
            if (x == 0) pos = neg = 0;
            else if (x > 0) {
                pos++;
                neg = neg > 0 ? neg + 1 : 0;
            } else {
                int tmp = pos;
                pos = neg > 0 ? neg + 1 : 0;
                neg = tmp > 0 ? tmp + 1 : 1;
            }
            ans = Math.max(ans, pos);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun getMaxLen(nums: IntArray): Int {
        var pos = 0
        var neg = 0
        var ans = 0
        for (x in nums) {
            if (x == 0) {
                pos = 0; neg = 0
            } else if (x > 0) {
                pos++
                neg = if (neg > 0) neg + 1 else 0
            } else {
                val tmp = pos
                pos = if (neg > 0) neg + 1 else 0
                neg = if (tmp > 0) tmp + 1 else 1
            }
            ans = maxOf(ans, pos)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def getMaxLen(self, nums: list[int]) -> int:
        pos = neg = ans = 0
        for x in nums:
            if x == 0:
                pos = neg = 0
            elif x > 0:
                pos += 1
                neg = neg + 1 if neg > 0 else 0
            else:
                tmp = pos
                pos = neg + 1 if neg > 0 else 0
                neg = tmp + 1 if tmp > 0 else 1
            ans = max(ans, pos)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn get_max_len(nums: Vec<i32>) -> i32 {
        let (mut pos, mut neg, mut ans) = (0, 0, 0);
        for &x in &nums {
            if x == 0 {
                pos = 0; neg = 0;
            } else if x > 0 {
                pos += 1;
                neg = if neg > 0 { neg + 1 } else { 0 };
            } else {
                let tmp = pos;
                pos = if neg > 0 { neg + 1 } else { 0 };
                neg = if tmp > 0 { tmp + 1 } else { 1 };
            }
            ans = ans.max(pos);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    getMaxLen(nums: number[]): number {
        let pos = 0, neg = 0, ans = 0;
        for (const x of nums) {
            if (x === 0) pos = neg = 0;
            else if (x > 0) {
                pos++;
                neg = neg > 0 ? neg + 1 : 0;
            } else {
                const tmp = pos;
                pos = neg > 0 ? neg + 1 : 0;
                neg = tmp > 0 ? tmp + 1 : 1;
            }
            ans = Math.max(ans, pos);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), since we process each element once.
  • 🧺 Space complexity: O(1), only a few variables are used.