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] <= 109Approach: We can iterate through the array while maintaining two counters: one for the length of the subarray when the product is positive (posCount) and another when it is negative (negCount). Each time we encounter a number, we adjust these counters based on whether the number is positive or negative.
When a zero is encountered, both counters are reset since any subarray including zero cannot yield a positive product. The aim is to keep track of the maximum posCount encountered, which indicates the maximum length of a subarray with a positive product.
This solution scans through the array and maintains two counts (posCount and negCount) to determine the maximum subarray length with a positive product. We update these counters based on whether the current number is positive, negative, or zero.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of elements in nums as we iterate through the array once.
Space Complexity: O(1), since we are using a constant amount of space.
Approach: We can approach the problem with a two-pass method, traversing the array twice: in the forward direction and reverse direction. During each traversal, we maintain counts of positive and negative products and update maximum lengths as required. This approach helps in scenarios where negative element pairs might yield positive results when considered in different subarrays formed during forward and backtracking.
This solution consists of two passes: a forward traversal followed by a backward traversal where we adjust positive and negative product counters. We track maximum subarray lengths in both directions to find the result.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), due to two separate linear traversals.
Space Complexity: O(1), as it uses a constant number of variables for tracking progress and computing the maximum length.
| Approach | Complexity |
|---|---|
| Greedy Approach With Signs | Time Complexity: O(n), where n is the number of elements in nums as we iterate through the array once. |
| Two-Pass Approach | Time Complexity: O(n), due to two separate linear traversals. |
Maximum Product Subarray - Dynamic Programming - Leetcode 152 • NeetCode • 452,961 views views
Watch 9 more video solutions →Practice Maximum Length of Subarray With Positive Product with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor