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.
For example:
nums = [1,-2,-3,4]
Output: 4
Explanation: The array nums already has a positive product of 24.
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.
nums = [-1,-2,-3,0,1]
Output: 2
Explanation: The longest subarray with positive product is [-1,-2]
or [-2,-3]
.
What is the most efficient algorithm to solve this problem? Consider edge cases and explain the time and space complexity.
A brute-force solution would involve iterating through all possible subarrays and checking if the product of each subarray is positive. We would keep track of the maximum length of such a subarray.
def max_len_brute_force(nums):
max_length = 0
for i in range(len(nums)):
for j in range(i, len(nums)):
product = 1
for k in range(i, j + 1):
product *= nums[k]
if product > 0:
max_length = max(max_length, j - i + 1)
return max_length
Time Complexity: O(n^3), where n is the length of the input array nums
. This is because we have nested loops to iterate through all possible subarrays, and another inner loop to calculate the product of each subarray.
Space Complexity: O(1), as we are only using a constant amount of extra space.
A more efficient solution involves using dynamic programming. We can keep track of the maximum length of positive and negative product subarrays ending at each index. Let pos[i]
be the maximum length of a positive product subarray ending at index i
, and neg[i]
be the maximum length of a negative product subarray ending at index i
.
nums[i] > 0
, then pos[i] = pos[i-1] + 1
and neg[i] = neg[i-1] + 1
if neg[i-1] > 0
, otherwise neg[i] = 0
.nums[i] < 0
, then pos[i] = neg[i-1] + 1
if neg[i-1] > 0
, otherwise pos[i] = 0
, and neg[i] = pos[i-1] + 1
.nums[i] == 0
, then pos[i] = 0
and neg[i] = 0
.We can optimize space by just using two variables to store the current positive and negative lengths instead of arrays.
def get_max_len(nums):
pos = 0
neg = 0
max_length = 0
for num in nums:
if num > 0:
pos += 1
neg = neg + 1 if neg > 0 else 0
elif num < 0:
new_pos = neg + 1 if neg > 0 else 0
new_neg = pos + 1
pos = new_pos
neg = new_neg
else:
pos = 0
neg = 0
max_length = max(max_length, pos)
return max_length
Time Complexity: O(n), where n is the length of the input array nums
. We iterate through the array only once.
Space Complexity: O(1), as we are only using a constant amount of extra space.