Solution to LeetCode 1567 Maximum Length of Subarray With Positive Product.
LeetCode 1567
Maximum Length of Subarray With Positive Product (Medium). [link]
We need to store the max length of positive product positive[i] and max length of negative product negative[i].
Base case: If it is an empty array, return 0. If there is only one element in the array. When nums$[0] > 0$ , positive$[0] = 1$. When nums$[0] < 0$, negative$[0]=1$.
Case 1: when nums$[i] > 0$,
positive[i] = positive[i-1]+1
negative[i] = negative[i-1]+1 if negative[i-1]>0, else if negative[i-1] = 0, negative[i] = 0.
Case 2: when nums$[i]<0$,
positive[i] = negative[i-1]+1 if negative[i-1]>0, else if negative[i-1] = 0, positive[i] = 0.
negative[i] = positive[i-1]+1
Note that if the product is zero, it’s impossible to get either positive product or negative product. This is already considered in case 1 and case 2.
The final answer the is max of the positive and negative.
class Solution(object):
def getMaxLen(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
positive, negative = [0] * n, [0] * n
if nums[0] > 0:
positive[0] = 1
elif nums[0] < 0:
negative[0] = 1
ans = positive[0]
for i in range(1,n):
if nums[i] > 0:
positive[i] = positive[i-1] + 1
negative[i] = (negative[i-1] + 1 if negative[i-1] > 0 else 0)
elif nums[i] < 0:
positive[i] = (negative[i-1] + 1 if negative[i-1] > 0 else 0)
negative[i] = positive[i-1] + 1
else:
positive[i] = negative[i] = 0
ans = max(ans, positive[i])
return ans
