Given an array arr[] consisting of n integers, find the length of the longest subarray with positive (non zero) product.
 
Example 1:
Input:
arr[] ={0, 1, -2, -3, -4} 
Output:
3
Explanation: 
The longest subarray with positive product is: 
{1, -2, -3}.Therefore, the required length is 3.
 
Example 2:
Input:
arr[]={-1, -2, 0, 1, 2}
Output:
2
Explanation:
The longest subarray with positive products 
are: {-1, -2}, {1, 2}. Therefore, the required 
length is 2.
 
Your Task: This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function maxLength() that takes array arr[], and an integer n as parameters and return the length of the longest subarray where the product of all of its element is positive. 
 
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).
 
Constraints:
 1<=n<=10^{5}
-10^{9}<=arr[i]<=10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3





class Solution:

    def maxLength(self,arr,n):

        #code here

Solutions:
from operator import itemgetter

class Solution:

	def maxLength(self, arr, n):
		hi = lo = 0
		max_count = 0
		for a in arr:
			if a == 0:
				hi = lo = 0
				continue
			elif a > 0:
				hi += 1
				lo = lo and lo + 1 or 0
			else:
				(hi, lo) = (lo and lo + 1 or 0, hi and hi + 1 or 1)
			max_count = max(max_count, hi)
		return max_count


def maxLenSub(arr, N):
	Pos = 0
	Neg = 0
	res = 0
	for i in range(N):
		if arr[i] == 0:
			Pos = Neg = 0
		elif arr[i] > 0:
			Pos += 1
			if Neg != 0:
				Neg += 1
			res = max(res, Pos)
		else:
			(Pos, Neg) = (Neg, Pos)
			Neg += 1
			if Pos != 0:
				Pos += 1
			res = max(res, Pos)
	return res

class Solution:

	def maxLength(self, arr, n):
		return maxLenSub(arr, n)


class Solution:

	def maxLength(self, arr, n):
		(pos_len, neg_len, ans) = (0, 0, 0)
		for e in arr:
			if e == 0:
				pos_len = neg_len = 0
			elif e < 0:
				(pos_len, neg_len) = (neg_len + 1 if neg_len else 0, pos_len + 1)
			else:
				(neg_len, pos_len) = (neg_len + 1 if neg_len else 0, pos_len + 1)
			ans = max(ans, pos_len)
		return ans


class Solution:

	def maxLength(self, arr, n):
		positive = 0
		negative = 0
		result = 0
		for i in range(n):
			if arr[i] == 0:
				positive = 0
				negative = 0
			elif arr[i] > 0:
				positive += 1
				if negative != 0:
					negative += 1
				result = max(result, positive)
			else:
				(positive, negative) = (negative, positive)
				negative += 1
				if positive != 0:
					positive += 1
				result = max(result, positive)
		result = max(result, positive)
		return result


class Solution:

	def maxLength(self, nums, n):
		(pos, neg) = ([0] * n, [0] * n)
		if nums[0] > 0:
			pos[0] = 1
		if nums[0] < 0:
			neg[0] = 1
		ans = pos[0]
		for i in range(1, n):
			if nums[i] > 0:
				pos[i] = 1 + pos[i - 1]
				neg[i] = 1 + neg[i - 1] if neg[i - 1] > 0 else 0
			elif nums[i] < 0:
				pos[i] = 1 + neg[i - 1] if neg[i - 1] > 0 else 0
				neg[i] = 1 + pos[i - 1]
			ans = max(ans, pos[i])
		return ans


class Solution:

	def maxLength(self, arr, N):
		le = 0
		new_le = 0
		max_le = 0
		for i in range(N):
			if arr[i] == 0:
				le = new_le = 0
			elif arr[i] > 0:
				le += 1
				if new_le != 0:
					new_le += 1
				max_le = max(max_le, le)
			else:
				(le, new_le) = (new_le, le)
				new_le += 1
				if le != 0:
					le += 1
				max_le = max(max_le, le)
		return max_le


class Solution:

	def maxLength(self, arr, n):
		left = 0
		negs = 0
		(curr_len, curr_prod) = (0, 0)
		max_len = 0
		while left < n and arr[left] == 0:
			left += 1
		if left == n:
			return 0
		for num in arr[left:]:
			if num < 0:
				negs += 1
		for right in range(left, n):
			if curr_prod > 0:
				max_len = max(max_len, curr_len)
			if curr_prod == 0 and arr[right] == 0:
				curr_len = 0
				curr_prod = 0
				left = right + 1
			elif curr_prod == 0 and arr[right] < 0:
				if negs > 1:
					curr_prod = -1
					curr_len = 1
					left = right
				else:
					curr_len = 0
					curr_prod = 0
					left = right + 1
				negs -= 1
			elif curr_prod == 0 and arr[right] > 0:
				curr_prod = 1
				curr_len = 1
				left = right
			elif arr[right] == 0:
				while left < right and curr_prod < 0:
					curr_prod /= arr[left] // abs(arr[left])
					curr_len -= 1
					left += 1
				if curr_len > 0:
					max_len = max(max_len, curr_len)
				curr_len = 0
				curr_prod = 0
			elif curr_prod > 0 and arr[right] > 0:
				curr_prod *= 1
				curr_len += 1
			elif curr_prod < 0 and arr[right] < 0:
				curr_prod *= -1
				curr_len += 1
				negs -= 1
			elif curr_prod < 0 and arr[right] > 0:
				while left < n and negs < 1:
					curr_prod /= arr[left] // abs(arr[left])
					curr_len -= 1
					if arr[left] < 0:
						negs += 1
					left += 1
				curr_prod *= 1
				curr_len += 1
			elif curr_prod > 0 and arr[right] < 0:
				while left < n and negs < 2:
					curr_prod /= arr[left] // abs(arr[left])
					curr_len -= 1
					if arr[left] < 0:
						negs += 1
					left += 1
				curr_prod *= -1
				curr_len += 1
				negs -= 1
		if curr_prod > 0:
			return max(max_len, curr_len)
		return max_len


class Solution:

	def maxLength(self, arr, n):
		firstNegative = -1
		length = 0
		indexZero = -1
		numberOfNegative = 0
		for i in range(n):
			if arr[i] == 0:
				firstNegative = -1
				indexZero = i
				numberOfNegative = 0
			elif arr[i] > 0:
				pass
			else:
				numberOfNegative += 1
				if firstNegative == -1:
					firstNegative = i
			if numberOfNegative % 2 == 0:
				length = max(length, i - indexZero)
			else:
				length = max(length, i - firstNegative)
		return length


class Solution:

	def maxLength(self, arr, n):

		def ans(arr):
			ans = 0
			n = 0
			for i in arr:
				if i < 0:
					n += 1
			if not n & 1:
				return len(arr)
			(f, l) = (10 ** 9, -10 ** 9)
			for i in range(len(arr)):
				if arr[i] < 0:
					f = min(f, i)
					l = max(l, i)
			return max(l, len(arr) - 1 - f)
		best = 0
		s = 0
		for i in range(len(arr)):
			if arr[i] == 0:
				best = max(best, ans(arr[s:i]))
				s = i + 1
			else:
				continue
		best = max(best, ans(arr[s:len(arr)]))
		return best


class Solution:

	def maxLength(self, arr, n):
		dp = []
		lastp = 0
		lastn = -1
		preffix = 1
		active = True

		def sign(x):
			if x > 0:
				return 1
			if x < 0:
				return -1
			return 0
		solve = 0
		for i in range(n):
			if preffix < 0 and lastn == -1:
				lastn = i - 1
			preffix *= arr[i]
			preffix = sign(preffix)
			if preffix == 0:
				lastp = i + 1
				lastn = -1
				preffix = 1
			elif preffix > 0:
				solve = max(solve, i - lastp + 1)
			elif lastn >= 0:
				solve = max(solve, i - lastn)
		return solve


class Solution:

	def maxLength(self, arr, n):
		ind = 0
		ans = 0
		while ind < n:
			if arr[ind] == 0:
				ind += 1
				continue
			negcnt = 0
			start = ind
			firstneg = -1
			lastneg = -1
			while ind < n and arr[ind] != 0:
				if arr[ind] < 0 and firstneg == -1:
					firstneg = ind
				if arr[ind] < 0:
					lastneg = ind
					negcnt += 1
				ind += 1
			if negcnt % 2 == 0:
				ans = max(ans, ind - start)
			else:
				ans = max(ans, ind - firstneg - 1, lastneg - start)
		return ans


class Solution:

	def maxLength(self, arr, n):
		(plen, nlen, ans) = (0, 0, 0)
		for i in arr:
			if i == 0:
				(plen, nlen) = (0, 0)
			elif i < 0:
				(plen, nlen) = (nlen + 1 if nlen else 0, plen + 1)
			else:
				(plen, nlen) = (plen + 1, nlen + 1 if nlen else 0)
			ans = max(ans, plen)
		return ans


class Solution:

	def maxLength(self, arr, n):
		start = 0
		end = 0
		maxlen = 0
		prev = 0
		negseen = 0
		while end < n:
			if arr[end] < 0:
				negseen = 1 + prev
			elif arr[end] > 0:
				negseen = prev
			else:
				negseen = 0
			prev = negseen
			if negseen == 0 and arr[end] == 0:
				end += 1
				start = end
				prev = 0
			elif negseen % 2 == 0:
				maxlen = max(maxlen, end - start + 1)
				end += 1
			else:
				end += 1
		start = n - 1
		end = n - 1
		negseen = 0
		prev = 0
		while end >= 0:
			if arr[end] < 0:
				negseen = 1 + prev
			elif arr[end] > 0:
				negseen = prev
			else:
				negseen = 0
			prev = negseen
			if negseen == 0 and arr[end] == 0:
				end -= 1
				start = end
				prev = 0
			elif negseen % 2 == 0:
				maxlen = max(maxlen, start - end + 1)
				end -= 1
			else:
				end -= 1
		return maxlen


class Solution:

	def maxLength(self, arr, n):
		s = 0
		e = s
		ne_c = 0
		maxlen = 0
		last_neg = 0
		while s < n:
			if e == n - 1:
				if arr[e] < 0:
					last_neg = e
					ne_c += 1
				if ne_c % 2 != 0:
					maxlen = max(maxlen, last_neg - s)
				elif arr[e] == 0:
					maxlen = max(maxlen, e - s)
				else:
					maxlen = max(maxlen, e + 1 - s)
				if arr[s] < 0:
					ne_c -= 1
				if s == e:
					e = e + 1
				s = s + 1
				continue
			if arr[e] == 0:
				if ne_c % 2 != 0:
					maxlen = max(maxlen, last_neg - s)
				else:
					maxlen = max(maxlen, e - s)
				if arr[s] < 0:
					ne_c -= 1
				if s == e:
					e = e + 1
				s = s + 1
				continue
				continue
			if arr[e] < 0:
				last_neg = e
				ne_c += 1
				e += 1
				continue
			e += 1
		return maxlen


class Solution:

	def maxLength(self, arr, n):
		max_len = 0
		start_ind = -1
		first_neg_ind = -1
		positive = True
		for i in range(n):
			if arr[i] > 0:
				if positive:
					max_len = max(max_len, i - start_ind)
				else:
					max_len = max(max_len, i - first_neg_ind)
			elif arr[i] < 0:
				positive = not positive
				if first_neg_ind == -1:
					first_neg_ind = i
				if positive:
					max_len = max(max_len, i - start_ind)
				else:
					max_len = max(max_len, i - first_neg_ind)
			else:
				first_neg_ind = -1
				positive = True
				start_ind = i
		return max_len


from math import inf

class Solution:

	def maxLength(self, arr, n):
		res = 0
		(neg_len, pos_len) = (-inf, -inf)
		for a in arr:
			if a == 0:
				(neg_len, pos_len) = (-inf, -inf)
			elif a > 0:
				(neg_len, pos_len) = (neg_len + 1, max(1, pos_len + 1))
			else:
				(neg_len, pos_len) = (max(1, pos_len + 1), neg_len + 1)
			res = max(res, pos_len)
		return res


class Solution:

	def maxLength(self, arr, n):
		pos_prod = 0
		neg_prod = 0
		long_cnt = 0
		for i in range(n):
			if arr[i] > 0:
				pos_prod += 1
				if neg_prod > 0:
					neg_prod += 1
				long_cnt = max(long_cnt, pos_prod)
			elif arr[i] < 0:
				(pos_prod, neg_prod) = (neg_prod, pos_prod)
				neg_prod += 1
				if pos_prod > 0:
					pos_prod += 1
				long_cnt = max(long_cnt, pos_prod)
			else:
				(pos_prod, neg_prod) = (0, 0)
		return long_cnt


class Solution:

	def maxLength(self, arr, n):
		(maxlen, prevzero, firstneg, nodd) = (0, -1, -1, 0)
		for i in range(n):
			if arr[i] < 0:
				nodd += 1
				if firstneg == -1:
					firstneg = i
			if arr[i] == 0:
				prevzero = i
				nodd = 0
				firstneg = -1
			elif nodd % 2 == 0:
				maxlen = max(maxlen, i - prevzero)
			else:
				maxlen = max(maxlen, i - firstneg)
		return maxlen


class Solution:

	def maxLength(self, arr, n):
		p = 0
		n = 0
		f = 0
		for i in arr:
			if i == 0:
				p = 0
				n = 0
			elif i < 0:
				(p, n) = (n + 1 if n else 0, p + 1)
			else:
				(n, p) = (n + 1 if n else 0, p + 1)
			f = max(p, f)
		return f


class Solution:

	def maxLength(self, arr, n):
		neg_count = 0
		fNeg = -1
		max_len = 0
		start = -1
		for i in range(0, n):
			if arr[i] == 0:
				start = i
				neg_count = 0
				fNeg = -1
			if arr[i] < 0:
				neg_count = neg_count + 1
				if fNeg == -1:
					fNeg = i
			if neg_count % 2 == 0:
				max_len = max(max_len, i - start)
			else:
				max_len = max(max_len, i - fNeg)
		return max_len


class Solution:

	def maxLength(self, arr, n):
		(negcount, prevzero, ans, firstneg) = (0, -1, 0, -1)
		for i in range(n):
			if arr[i] == 0:
				firstneg = -1
				prevzero = i
				negcount = 0
			if arr[i] < 0:
				if firstneg == -1:
					firstneg = i
				negcount += 1
			if negcount % 2 == 0:
				ans = max(ans, i - prevzero)
			else:
				ans = max(ans, i - firstneg)
		if negcount % 2 == 0:
			ans = max(ans, i - prevzero)
		else:
			ans = max(ans, i - firstneg)
		return ans


from sys import maxsize

class Solution:

	def maxLength(self, arr, n):
		dp = []
		pos = neg = 0
		pos = 1 if arr[0] > 0 else pos
		neg = 1 if arr[0] < 0 else neg
		max_pos = pos
		for index in range(1, len(arr)):
			if arr[index] == 0:
				pos = 0
				neg = 0
			elif arr[index] > 0:
				pos += 1
				neg = 1 + neg if neg > 0 else 0
			elif arr[index] < 0:
				temp = neg
				neg = 1 + pos
				pos = 1 + temp if temp > 0 else 0
			max_pos = max(max_pos, pos)
		return max_pos


class Solution:

	def maxLength(self, arr, n):
		ne = 0
		j = 0
		ans = 0
		for i in range(n):
			while j < n and (arr[j] != 0 or j < i):
				if arr[j] < 0:
					ne += 1
				j += 1
				if ne & 1 == 0:
					ans = max(ans, j - i)
			if ne & 1 == 0:
				ans = max(ans, j - i)
			if arr[i] < 0:
				ne -= 1
		return ans


def solve(a):
	neg = 0
	for i in a:
		if i < 0:
			neg += 1
	if neg % 2 == 0:
		return len(a)
	else:
		i = 0
		while i < len(a) and a[i] > 0:
			i += 1
		j = len(a) - 1
		while j >= 0 and a[j] > 0:
			j -= 1
		j = len(a) - 1 - j
		return max(len(a) - i - 1, len(a) - j - 1)

class Solution:

	def maxLength(self, arr, n):
		zeros = [-1]
		for i in range(n):
			if arr[i] == 0:
				zeros.append(i)
		zeros.append(n)
		ans = 0
		for i in range(len(zeros) - 1):
			x = zeros[i] + 1
			y = zeros[i + 1] - 1
			if y >= x:
				ans = max(ans, solve(arr[x:y + 1]))
		return ans


class Solution:

	def maxLength(self, arr, n):
		length = 0
		pos = 0
		Neg = 0
		res = 0
		for i in range(n):
			if arr[i] == 0:
				pos = Neg = 0
			elif arr[i] > 0:
				pos += 1
				if Neg != 0:
					Neg += 1
				res = max(pos, res)
			else:
				(pos, Neg) = (Neg, pos)
				Neg += 1
				if pos != 0:
					pos += 1
				res = max(res, pos)
		return res


class Solution:

	def maxLength(self, arr, n):
		a = arr.copy()
		d = {}
		odd = 0
		eve = 0
		k = 0
		j = 0
		neg = 0
		for i in range(n):
			if a[i] < 0:
				neg += 1
			if a[i] == 0 or i == n - 1:
				if a[i] and i == n - 1:
					x = i + 1
				else:
					x = i
				d[j] = (a[k:x], x - k, neg)
				j += 1
				k = i + 1
				neg = 0
		for p in d:
			(s, l, neg) = d[p]
			if l:
				m = 0
				n = 0
				if neg % 2:
					for i in range(l):
						if s[i] > 0:
							m += 1
						else:
							m += 1
							break
					for i in range(l - 1, -1, -1):
						if s[i] > 0:
							n += 1
						else:
							n += 1
							break
					x = max(l - m, l - n)
					if odd < x:
						odd = x
				elif eve < l:
					eve = l
		return max(odd, eve)


class Solution:

	def maxLength(self, arr, n):
		maxLen = 0
		negCount = 0
		firstNeg = -1
		prevZero = -1
		lastNeg = 0
		prevMax = 0
		for i in range(n):
			if arr[i] < 0:
				if firstNeg == -1:
					firstNeg = i
				negCount += 1
				lastNeg = i
			if arr[i] == 0:
				prevMax = maxLen
				maxLen = 0
				negCount = 0
				firstNeg = -1
				prevZero = i
			if negCount % 2 == 0 or negCount == 0:
				maxLen = max(prevMax, maxLen, i - prevZero)
			else:
				maxLen = max(prevMax, maxLen, i - firstNeg, lastNeg - firstNeg)
		return maxLen


class Solution:

	def count_negatives(self, arr, start_index, length):
		return sum((arr[i] < 0 for i in range(start_index, start_index + length)))

	def find_outermost_negative_reduction(self, arr, start_index, length):
		for i in range(length):
			if arr[start_index + i] < 0 or arr[start_index + length - i - 1] < 0:
				return i
		return 0

	def maxLength(self, arr, n):
		max_length = 0
		subarray_start_index = 0
		while subarray_start_index < n:
			try:
				next_zero = arr.index(0, subarray_start_index)
			except ValueError:
				next_zero = n
			subarray_length = next_zero - subarray_start_index
			if self.count_negatives(arr, subarray_start_index, subarray_length) % 2:
				subarray_length -= self.find_outermost_negative_reduction(arr, subarray_start_index, subarray_length) + 1
			subarray_start_index = next_zero + 1
			max_length = max(subarray_length, max_length)
		return max_length


class Solution:

	def maxLength(self, nums, n):
		(a, b) = (0, 0)
		mx = 0
		(neg, pos) = (0, 0)
		zero = [0, 0]
		flag = False
		for i in range(n):
			if nums[i] < 0:
				neg += 1
				if zero[1] == zero[0]:
					zero[1] = i + 1
				b = i + 1
			elif nums[i] == 0:
				(pos, neg) = (0, 0)
				zero = [i + 1, i + 1]
			else:
				pos += 1
			if neg & 1:
				mx = max(mx, i - zero[1] + 1)
			else:
				mx = max(mx, i - zero[0] + 1)
		return mx


class Solution:

	def maxLength(self, arr, n):
		if n == 1:
			if arr[0] <= 0:
				return 0
			else:
				return 1
		count = maxcount = 0
		ncount = 0
		prcount = nrcount = 0
		firstneg = ''
		for i in range(n):
			if arr[i] == 0:
				count = 0
				ncount = 0
				prcount = 0
				nrcount = 0
				firstneg = ''
				continue
			if arr[i] < 0:
				if firstneg == '':
					firstneg = i
				count = 0
				ncount += 1
				nrcount += 1
			if ncount == 1:
				maxcount = max(maxcount, i - firstneg)
			elif ncount == 2:
				count = nrcount + prcount
				ncount = 0
			if arr[i] > 0:
				count += 1
				prcount += 1
			if count > maxcount:
				maxcount = count
		return maxcount


class Solution:

	def maxLength(self, arr, n):
		if n == 1:
			if arr[0] <= 0:
				return 0
			else:
				return 1
		count = maxcount = 0
		ncount = 0
		prcount = nrcount = 0
		isneg = False
		firstneg = ''
		prevzero = -1
		for i in range(n):
			if arr[i] == 0:
				currprod = 1
				count = 0
				ncount = 0
				prevzero = i
				prcount = 0
				nrcount = 0
				firstneg = ''
				continue
			if arr[i] < 0:
				if firstneg == '':
					firstneg = i
				count = 0
				isneg = True
				ncount += 1
				nrcount += 1
			if ncount == 1:
				maxcount = max(maxcount, i - firstneg)
			elif ncount == 2:
				count = nrcount + prcount
				ncount = 0
			if arr[i] > 0:
				isneg = False
				count += 1
				prcount += 1
			if count > maxcount:
				maxcount = count
		return maxcount


class Solution:

	def maxLength(self, arr, n):
		start = 0
		neg = -1
		countNeg = 0
		ans = 0
		curr = 1
		for i in range(0, n):
			if arr[i] == 0:
				if countNeg % 2 == 0:
					ans = max(ans, i - start)
				else:
					ans = max(ans, i - neg - 1)
				start = i + 1
				neg = -1
				countNeg = 0
				continue
			if arr[i] < 0:
				countNeg += 1
				if neg < 0:
					neg = i
			if countNeg % 2 == 0:
				ans = max(ans, i - start + 1)
			else:
				ans = max(ans, i - neg)
		return ans


class Solution:

	def maxLength(self, arr, n):
		n = len(arr)
		(i, j) = (0, 0)
		ans = 0
		nc = 0
		while j < n:
			if arr[j] < 0:
				nc += 1
				j += 1
			elif arr[j] == 0:
				if nc % 2 == 0:
					i = j + 1
					j = i
				else:
					if arr[i] < 0:
						nc -= 1
					i += 1
			else:
				j += 1
			if nc % 2 == 0:
				ans = max(ans, j - i)
		if nc % 2 == 1:
			while i < n and arr[i] > 0:
				i += 1
			ans = max(ans, j - i - 1)
		else:
			ans = max(ans, j - i)
		return ans


class Solution:

	def maxLength(self, arr, n):
		length1 = 0
		length2 = 0
		length = 0
		temp = 0
		pod = 1
		for i in range(n):
			if arr[i] == 0:
				temp = 0
				pod = 1
				continue
			if arr[i] > 0:
				pod = pod * 1
			else:
				pod = pod * -1
			temp = temp + 1
			if pod > 0:
				length1 = max(length1, temp)
		length = 0
		temp = 0
		pod = 1
		for i in range(1, n):
			if arr[n - i] == 0:
				temp = 0
				pod = 1
				continue
			if arr[n - i] > 0:
				pod = pod * 1
			else:
				pod = pod * -1
			temp = temp + 1
			if pod > 0:
				length2 = max(length2, temp)
		length = max(length1, length2)
		return length


class Solution:

	def maxLength(self, arr, n):
		ans = 0
		cur_pos = 0
		cur_neg = 0
		for x in arr:
			if x == 0:
				cur_pos = 0
				cur_neg = 0
			if x > 0:
				cur_pos += 1
				if cur_neg:
					cur_neg += 1
			if x < 0:
				tmp = cur_neg
				cur_neg = cur_pos + 1
				if tmp:
					cur_pos = tmp + 1
				else:
					cur_pos = 0
			ans = max(ans, cur_pos)
		return ans


class Solution:

	def maxLength(self, arr, n):
		neg = 0
		ans = 0
		fneg = -1
		pzero = -1
		for i in range(n):
			val = arr[i]
			if val < 0:
				neg += 1
				if fneg == -1:
					fneg = i
			if val == 0:
				neg = 0
				fneg = -1
				pzero = i
			elif neg % 2 == 0:
				ans = max(ans, i - pzero)
			else:
				ans = max(ans, i - fneg)
		return ans


class Solution:

	def maxLength(self, arr, n):
		maxLenght = 0
		firstNeg = float('inf')
		lastNeg = float('-inf')
		Count = 0
		NegNum = 0
		for (ind, value) in enumerate(arr):
			if value == 0:
				maxLenght = max(maxLenght, lastNeg - firstNeg)
				firstNeg = float('inf')
				lastNeg = float('-inf')
				Count = 0
				NegNum = 0
			elif value < 0:
				Count += 1
				firstNeg = min(Count, firstNeg)
				lastNeg = max(lastNeg, Count)
				NegNum = (NegNum + 1) % 2
				if NegNum == 0:
					maxLenght = max(maxLenght, Count)
			else:
				Count += 1
				if NegNum == 0:
					maxLenght = max(maxLenght, Count)
				else:
					maxLenght = max(maxLenght, Count - firstNeg)
		return maxLenght


class Solution:

	def maxLength(self, arr, n):
		count_neg = 0
		first_neg = -1
		count_max = 0
		(i, j) = (0, 0)
		while j < n and i <= j:
			if arr[j] == 0:
				count_neg = 0
				first_neg = -1
				i = j + 1
			else:
				if arr[j] < 0 and first_neg == -1:
					first_neg = j
					count_neg += 1
				elif arr[j] < 0:
					count_neg += 1
				if count_neg % 2 == 0:
					count_max = max(count_max, j - i + 1)
				else:
					count_max = max(count_max, j - first_neg, first_neg - i)
			j += 1
		return count_max


class Solution:

	def maxLength(self, arr, n):
		curr_max = 0
		last_zero = -1
		curr_negatives = 0
		first_neg = -1
		for (i, num) in enumerate(arr):
			if num < 0:
				curr_negatives += 1
				if first_neg == -1:
					first_neg = i
			if num == 0:
				last_zero = i
				curr_negatives = 0
				first_neg = -1
			elif curr_negatives % 2 == 0:
				curr_max = max(curr_max, i - last_zero)
			else:
				curr_max = max(curr_max, i - first_neg)
		return curr_max


class Solution:

	def maxLength(self, arr, n):
		max_len = 0
		neg_count = 0
		start = 0
		end = 0
		Bmax_len = 0
		Bneg_count = 0
		Bstart = n - 1
		Bend = 0
		for i in range(n):
			if arr[i] == 0:
				start = i + 1
				neg_count = 0
			else:
				if arr[i] < 0:
					neg_count += 1
				end = i
				if neg_count % 2 == 0 and end - start + 1 > max_len:
					max_len = end - start + 1
			if arr[n - 1 - i] == 0:
				Bstart = n - 1 - i - 1
				Bneg_count = 0
			else:
				if arr[n - 1 - i] < 0:
					Bneg_count += 1
				Bend = n - 1 - i
				if Bneg_count % 2 == 0 and Bstart - Bend + 1 > Bmax_len:
					Bmax_len = Bstart - Bend + 1
		return max(max_len, Bmax_len)


class Solution:

	def maxLength(self, arr, n):
		beg = res = 0
		negs = True
		for end in range(n + 1):
			if end != n and arr[end] != 0:
				if arr[end] < 0:
					negs = not negs
				if negs:
					res = max(res, end - beg + 1)
			else:
				while beg < end:
					if arr[beg] < 0:
						negs = not negs
					if negs:
						res = max(res, end - beg - 1)
					beg += 1
				beg = end + 1
				negs = True
		return res


class Solution:

	def maxLength(self, arr, n):
		p = 1
		t = 0
		l = 0
		for i in arr:
			if i == 0:
				p = 1
				t = 0
			elif i > 0:
				p *= 1
				t += 1
			else:
				p *= -1
				t += 1
			if p == 1:
				l = max(l, t)
		p1 = 1
		t1 = 0
		l1 = 0
		for i in range(n - 1, -1, -1):
			if arr[i] == 0:
				p1 = 1
				t1 = 0
			elif arr[i] > 0:
				p1 *= 1
				t1 += 1
			else:
				p1 *= -1
				t1 += 1
			if p1 == 1:
				l1 = max(l1, t1)
		return max(l1, l)


class Solution:

	def maxLength(self, arr, n):
		pl = 0
		nl = 0
		fl = 0
		for i in arr:
			if i == 0:
				pl = 0
				nl = 0
			elif i < 0:
				(pl, nl) = (nl + 1 if nl else 0, pl + 1)
			else:
				(nl, pl) = (nl + 1 if nl else 0, pl + 1)
			fl = max(fl, pl)
		return fl


class Solution:

	def maxLength(self, arr, n):
		(pl, nl) = (0, 0)
		ans = 0
		for el in arr:
			if el == 0:
				pl = nl = 0
			elif el < 0:
				(pl, nl) = (nl + 1 if nl else 0, pl + 1)
			else:
				(nl, pl) = (nl + 1 if nl else 0, pl + 1)
			ans = max(ans, pl)
		return ans


class Solution:

	def maxLength(self, ar, n):
		cnt = 0
		cntr = []
		l = r = 0
		negl = negr = None
		negcnt = 0
		ans = float('-inf')
		for (i, num) in enumerate(ar):
			if num == 0:
				if not negcnt & 1:
					ans = max(cnt, ans)
					cnt = 0
					negcnt = 0
					l = i + 1
					r = i + 1
					negl = negr = None
					continue
				cur = cnt - (negl - l + 1)
				cur2 = cnt - (r - negr)
				ans = max(ans, cur, cur2)
				cnt = 0
				negcnt = 0
				l = i + 1
				r = i + 1
				negl = negr = None
			else:
				r += 1
				if num < 0:
					if negl is None:
						negl = i
					negr = i
					negcnt += 1
				cnt += 1
		if not negcnt & 1:
			ans = max(cnt, ans)
			return ans
		cur = cnt - (negl - l + 1)
		cur2 = cnt - (r - negr)
		ans = max(ans, cur, cur2)
		return ans


class Solution:

	def maxLength(self, arr, n):
		(zer, neg, cnt) = (-1, -1, 0)
		ans = 0
		for i in range(len(arr)):
			if arr[i] < 0:
				cnt += 1
				if neg == -1:
					neg = i
			if arr[i] == 0:
				zer = i
				neg = -1
				cnt = 0
			elif cnt % 2 == 0:
				ans = max(ans, i - zer)
			else:
				ans = max(ans, i - neg)
		return ans


class Solution:

	def maxLength(self, arr, n):
		ans = pos = neg = 0
		for num in arr:
			if num > 0:
				pos += 1
				neg += 1 if neg else 0
			elif num < 0:
				(pos, neg) = (1 + neg if neg else 0, 1 + pos)
			else:
				pos = neg = 0
			ans = max(ans, pos)
		return ans


class Solution:

	def maxLength(self, arr, n):
		neg_cnt = 0
		lastStart = -1
		firstNeg = -1
		setFirstNeg = True
		ans = 0
		for i in range(n):
			if arr[i] < 0:
				neg_cnt += 1
				if setFirstNeg:
					firstNeg = i
					setFirstNeg = False
			elif arr[i] == 0:
				setFirstNeg = True
				firstNeg = i
				lastStart = i
				neg_cnt = 0
			if neg_cnt % 2 == 0:
				ans = max(ans, i - lastStart)
			else:
				ans = max(ans, i - firstNeg)
		return ans


class Solution:

	def maxLength(self, arr, n):
		left = 0
		res = 0
		right = 0
		while right < n:
			first = -1
			second = -1
			count = 0
			while right < n and arr[right] != 0:
				if arr[right] < 0:
					count += 1
					if first == -1:
						first = right
					else:
						second = right
				right += 1
			if 1:
				if count % 2 == 0:
					res = max(res, right - left)
				else:
					if first != -1:
						res = max(res, right - first - 1, first - left)
					if second != -1:
						res = max(res, second - left, right - second - 1)
				if right < n and arr[right] == 0:
					right += 1
					left = right
		return res


class Solution:

	def maxLength(self, arr, n):
		pos = 0
		neg = 0
		res = 0
		for i in range(n):
			if arr[i] == 0:
				pos = neg = 0
			elif arr[i] > 0:
				pos += 1
				if neg != 0:
					neg += 1
				res = max(res, pos)
			else:
				t = pos
				pos = neg
				neg = t
				neg += 1
				if pos != 0:
					pos += 1
				res = max(res, pos)
		return res


class Solution:

	def maxLength(self, arr, n):
		prod = 1
		temp = 0
		maxLen = 0
		for i in range(n):
			if arr[i] == 0:
				temp = 0
				prod = 1
				continue
			if arr[i] > 0:
				prod *= 1
			else:
				prod *= -1
			temp += 1
			if prod > 0:
				maxLen = max(maxLen, temp)
		prod = 1
		temp = 0
		for i in reversed(range(n)):
			if arr[i] == 0:
				temp = 0
				prod = 1
				continue
			if arr[i] > 0:
				prod *= 1
			else:
				prod *= -1
			temp += 1
			if prod > 0:
				maxLen = max(maxLen, temp)
		return maxLen


class Solution:

	def maxLength(self, arr, n):
		maxi = 0
		neg = 0
		prev = -1
		fir = -1
		for ind in range(n):
			if arr[ind] < 0:
				neg += 1
				if fir == -1:
					fir = ind
			if arr[ind] == 0:
				fir = -1
				neg = 0
				prev = ind
			elif neg % 2 == 0:
				maxi = max(maxi, ind - prev)
			else:
				maxi = max(maxi, ind - fir)
		return maxi


class Solution:

	def maxLength(self, arr, n):
		(neg, negcount, count, start) = (-1, 0, 0, 0)
		for i in range(n):
			if arr[i] == 0:
				start = i + 1
				negcount = 0
				neg = -1
				continue
			if arr[i] < 0:
				negcount += 1
				if neg == -1:
					neg = i
			if negcount % 2 == 0:
				count = max(count, i - start + 1)
			else:
				count = max(count, i - neg)
		return count


class Solution:

	def maxLength(self, arr, n):
		i = 0
		res = 0
		while i < n:
			s = i
			while s < n and arr[s] == 0:
				s += 1
			e = s
			sn = en = -1
			c = 0
			while e < n and arr[e] != 0:
				if arr[e] < 0:
					c += 1
					if sn == -1:
						sn = e
					en = e
				e += 1
			if c % 2 == 0:
				res = max(res, e - s)
			elif s != -1:
				res = max(res, e - sn - 1, en - s)
			i = e + 1
		return res