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].

Example 4:
Input: nums = [-1,2]
Output: 1

Example 5:
Input: nums = [1,2,3,5,-6,4,0,10]
Output: 4

 
Constraints:

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Difficulty: interview

Starter code:

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        maxx = 0
        nums.append(0)
        
        # starting position
        # where we find a 0
        i = -1
        minusarr = []
        
        for j,n in enumerate(nums):
            if n == 0:
                # now figure out previous ones
                tot = j-i-1
                if not minusarr or len(minusarr)%2 == 0:
                    maxx = max(maxx, tot)
                else:
                    # drop the first or last 0
                    left = minusarr[0]-i
                    right = j-minusarr[-1]
                    maxx = max(maxx, tot - min(left, right))
                
                # reinitiate
                minusarr = []
                i = j
            elif n < 0:
                minusarr.append(j)
        return maxx

class Solution:
    def getMaxLen(self, a: List[int], having_zero=True) -> int:
        if not a: return 0
        if having_zero: 
            zeros = [i for i, x in enumerate(a) if x == 0]        
            ans, prev = -float('inf'), 0            
            for i in zeros:
                ans = max(ans, self.getMaxLen(a[prev:i], False))
                prev = i+1
            ans = max(ans, self.getMaxLen(a[prev:], False))
            return ans        
        negs = [i for i, x in enumerate(a) if x < 0]
        if len(negs) % 2 == 0: return len(a)
        return max(negs[-1], len(a) - negs[0] - 1)

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        # Greedy alg
        l = len(nums)
        start = 0
        subArrays = []
        for i in range(l):
            if nums[i] == 0:
                subArrays.append(self.findOptimal(nums[start:i]))
                start = i+1
                end = i+1
        
        subArrays.append(self.findOptimal(nums[start:l]))
        
        return max(subArrays)
    
    def findOptimal(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        negs = 0
        l = 0
        for i in nums:
            l += 1
            if i < 0: negs += 1
        
        if negs % 2 == 0:
            return l
        else:
            # Two pointers approach
            i = 0
            j = l - 1
            while i < j:
                if nums[i] < 0 or nums[j] < 0:
                    return l - 1
                i += 1
                j -= 1
                l -= 1
        
        #return max(self.findOptimal(nums[1:]), self.findOptimal(nums[:-1]))
        return 0

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        
        pos_p=0
        neg_p=0
        
        pos,neg=0,0
        
        result=0
        for i in range( len(nums)):
            
            pos_p,neg_p=pos,neg
            
            if nums[i] > 0:
                pos= 1 + pos_p
                neg= 1 + neg_p if neg_p > 0 else 0
                
            elif nums[i] < 0:
                pos= (1 + neg_p) if neg_p > 0 else 0
                neg= (1 + pos_p) if pos_p > 0 else 1
            else:
                pos,neg=0,0
            result=max(result, pos)
            
        return result

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        # 3:58 9/1/2020
        # Max len of subarray with positive Product
        
        last={1:-1}
        pro=1
        ans=0
        for i,c in enumerate(nums):
            pro = c * pro / abs(pro) if pro != 0 else 0
            
            if pro>0:
                ans=max(i-last[1],ans)
                
            elif pro<0:
                if -1 in last:
                    ans=max(ans,i-last[-1])
                else:
                    last[-1]=i
            elif pro==0:
                pro=1
                last={}
                last[1]=i
          
        return ans 
                        
                    
                
        
        
 
        

                    
                    
                    
                    
                
            
        


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[0] * (n+1) for i in range(2)]
        for i, x in enumerate(nums):
            if x > 0:
                dp[0][i+1] = dp[0][i] + 1
                if dp[1][i] > 0:
                    dp[1][i+1] = dp[1][i] + 1
            elif x < 0:
                if dp[1][i] > 0:
                    dp[0][i+1] = dp[1][i] + 1
                dp[1][i+1] = dp[0][i] + 1
            else:
                dp[0][i+1] = dp[1][i+1] = 0
                
        # print(dp)
        return max(dp[0])


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n=len(nums)
        pos,neg=0,0
        [0,1,-2,-3,-4]
        if nums[0]>0:
            pos=1
        if nums[0]<0:
            neg=1
        ans=pos
        for i in range(1,n):
            if nums[i]>0:
                pos = 1 + pos
                neg = 1 + neg if neg >0 else 0
            elif nums[i]<0:
                pre_pos,pre_neg=pos,neg
                pos= 1 + pre_neg if pre_neg >0 else 0
                neg = 1 + pre_pos
            else:
                pos,neg =0,0
            ans = max(ans,pos)
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        plus,minus,res,c = 0,-1,0,0
        for i in range(0,len(nums)):
            if nums[i] == 0:
                if c%2 == 1:
                    res = max(res,minus)
                else:
                    res = max(res,max(plus,minus))
                plus,minus,c = 0,-1,0
            elif nums[i] > 0:
                if minus != -1: 
                    minus += 1
                plus += 1
            else:
                c += 1
                minus += 1
                if c%2 == 1:
                    res = max(res,max(minus,plus))
                plus += 1
        if c%2 == 1:
            res = max(res,minus)
        else:
            res = max(res,max(plus,minus))
        return res
        


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        n = len(nums)
        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 getMaxLen(self, nums: List[int]) -> int:
        def solve(nums):
            cnt = 0
            for n in nums:
                if n < 0:
                    cnt += 1
            if cnt%2 == 0:
                return len(nums)
            for i in range(len(nums)):
                if nums[i] < 0:
                    first = i
                    break
            for i in range(len(nums)-1, -1, -1):
                if nums[i] < 0:
                    last = i
                    break
            return max(last, len(nums)-first-1)
        
        l = 0
        ans = 0
        nums.append(0)
        for r in range(len(nums)):
            if nums[r] == 0:
                cur = solve(nums[l:r])
                ans = max(ans, cur)
                l = r+1
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        @lru_cache(None)
        def pos_helper(len):
            if len == 0:
                return 0
            if len == 1:
                return 1 if nums[0] > 0 else 0
            if nums[len - 1] > 0:
                return pos_helper(len - 1) + 1
            if nums[len - 1] == 0:
                return 0
            if nums[len - 1] < 0:
                return neg_helper(len - 1) + 1 if neg_helper(len - 1) != 0 else 0

        @lru_cache(None)
        def neg_helper(len):
            if len == 0:
                return 0
            if len == 1:
                return 1 if nums[0] < 0 else 0
            if nums[len - 1] > 0:
                return neg_helper(len - 1) + 1 if neg_helper(len - 1) > 0 else 0
            if nums[len - 1] == 0:
                return 0
            if nums[len - 1] < 0:
                return pos_helper(len - 1) + 1

        res = 0
        for i in range(0, len(nums) + 1):
            res = max(res, pos_helper(i))
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        pos, neg = 0, 0
        if nums[0] > 0: pos = 1
        if nums[0] < 0: neg = 1
        ans = pos
        for i in range(1, n):
            if nums[i] > 0:
                pos_next = 1 + pos
                neg_next = 1 + neg if neg > 0 else 0
            elif nums[i] < 0:
                pos_next = 1 + neg if neg > 0 else 0
                neg_next = 1 + pos
            else:
                pos_next, neg_next = 0, 0
            pos, neg = pos_next, neg_next
            ans = max(ans, pos)
        return ans


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        maxlen = 0
        curlen = 0
        tmplen = 0
        even = True 
        for i in nums:
            if i == 0:
                if tmplen != curlen:
                    # We meet odd numbers of negative number, check if the rest is larger
                    maxlen = max(maxlen, tmplen - curlen - 1)
                maxlen = max(maxlen, curlen)
                curlen = 0
                tmplen = 0
                even = True
                continue
            tmplen += 1    
            if i < 0:    
                even = not even
                if even == True:
                    curlen = tmplen        
            if i > 0 and even == True:
                curlen += 1      
        if tmplen != curlen:
            # We meet odd numbers of negative number, check if the rest is larger
            maxlen = max(maxlen, tmplen - curlen - 1)
        maxlen = max(maxlen, curlen)        
        
        curlen = 0
        tmplen = 0
        even = True 
        for i in reversed(nums):
            if i == 0:
                if tmplen != curlen:
                    # We meet odd numbers of negative number, check if the rest is larger
                    maxlen = max(maxlen, tmplen - curlen - 1)
                maxlen = max(maxlen, curlen)
                curlen = 0
                tmplen = 0
                even = True
                continue
            tmplen += 1    
            if i < 0:    
                even = not even
                if even == True:
                    curlen = tmplen        
            if i > 0 and even == True:
                curlen += 1      
        if tmplen != curlen:
            # We meet odd numbers of negative number, check if the rest is larger
            maxlen = max(maxlen, tmplen - curlen - 1)
        maxlen = max(maxlen, curlen)        
        
        return maxlen       


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        pos = 1 if nums[0]>0 else 0
        neg = 1 if nums[0]<0 else 0
        
        ans = pos
        
        for i in range(1,len(nums)):
            if nums[i]>0:
                pos = 1+pos
                neg = 1+neg if neg>0 else 0
            elif nums[i]<0:
                pre_pos = pos
                pos = 1+neg if neg>0 else 0
                neg = 1+pre_pos
            else:
                pos, neg = 0, 0
                
            ans = max(ans,pos)
            
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        result = 0
        negativeIndices = []
        currentProduct = 1
        startIndex = 0
        
        for index,number in enumerate(nums):
            if number == 0:
                negativeIndices = []
                currentProduct = 1
                startIndex = index + 1
                continue
        
            if number * currentProduct > 0:
                result = max(result,index-startIndex+1)
                currentProduct = 1
            
            else: 
                if len(negativeIndices) != 0:
                    result = max(result,index-negativeIndices[0])
                currentProduct = -1
            
            if number < 0 and len(negativeIndices) == 0:
                negativeIndices.append(index)
  
        return result

class Solution:
    def getMaxLen(self, A: List[int], cnt = 0, best = 0) -> int:
        A.append(0)                    # ⭐️ sentinel value
        N = len(A)
        i = 0
        j = 0
        while i < N:
            while j < N and not A[j]:  # ➖ case 1: collapse window [i \\U0001f449 ..j]
                while i < j:
                    cnt = cnt - 1 if A[i] < 0 else cnt; i += 1
                    best = best if cnt & 1 else max(best, j - i)
                i = j + 1
                j = j + 1
            while j < N and A[j]:      # ➕ case 2: expand window [i..j \\U0001f449 ]
                cnt = cnt + 1 if A[j] < 0 else cnt; j += 1
                best = best if cnt & 1 else max(best, j - i)
        return best
    
    
    


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        pos = 0
        neg = 0
        negIndex = 0
        res = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                pos = 0
                neg = 0
            elif nums[i] > 0:
                pos += 1
            else:
                neg += 1
                if neg == 1:
                    negIndex = i
                
            if neg % 2 == 0:
                res = max(res, pos + neg)
            else:
                res = max(res, i - negIndex)
        return res 


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        pointer1=0
        pointer2=0
        res=0
        while(pointer1<len(nums)):
            if nums[pointer1]==0:
                pointer1+=1
                continue
            pointer2=pointer1
            count=0
            start=0
            end=0
            while(pointer2<len(nums) and nums[pointer2]!=0):
                if nums[pointer2]<0:
                    count+=1
                    if count==1:
                        start=pointer2
                    end=pointer2
                pointer2+=1
            if count%2==0:
                res=max(res,pointer2-pointer1)
            else:
                res=max(res,end-pointer1,pointer2-start-1)
            pointer1=pointer2
            
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        if not nums: return 0

        n = len(nums)
        negNum = 0
        firstNegIdx = -1
        zeroPos = -1
        res = 0
        
        for i, num in enumerate(nums):
            if num < 0:
                negNum += 1
                if firstNegIdx < 0: firstNegIdx = i
            
            if num == 0:
                negNum = 0
                firstNegIdx = -1
                zeroPos = i
            else:
                if negNum % 2 == 0:
                    res = max(res, i - zeroPos)
                else:
                    res = max(res, i - firstNegIdx)
                    
        return res


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        res, pos, neg = 0, 0, 0
        for num in nums:
            if num == 0:
                pos, neg = 0, 0
            elif num > 0:
                if neg != 0: neg, pos = neg+1, pos+1
                else: neg, pos = 0, pos+1
            else:
                if neg != 0: pos, neg = neg+1, pos+1
                else: neg, pos = pos+1, 0
            res = max(res, pos)
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        ans=0
        mn=0
        mp=0
        for i in nums:
            if i==0:
                mn,mp=0,0
            elif i>0:
                mp+=1
                if mn!=0:
                    mn+=1
                else:mn=0
            else:
                omn=mn
                mn=mp+1
                if omn!=0:
                    mp=omn+1
                else:
                    mp=0
            ans=max(mp,ans)
        return ans
                    


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        # dp = [[0 for i in range(2)]  for j in  range(len(nums) + 1)]
        # res = 0
        # for i, num in enumerate(nums):
        #     if num == 0:
        #         dp[i + 1][0] = dp[i + 1][1] = 0
        #     elif num > 0:
        #         dp[i + 1][0] = dp[i][0] + 1
        #         dp[i + 1][1] = dp[i][1] + 1 if dp[i][1] else 0
        #     else:
        #         dp[i + 1][0] = dp[i][1] + 1 if dp[i][1] else 0
        #         dp[i + 1][1] = dp[i][0] + 1
        #     res = max(res, dp[i + 1][0])
        # return res
        pos_num = neg_num = res = 0
        for i, num in enumerate(nums):
            if num == 0:
                pos_num = neg_num = 0
            elif num > 0:
                neg_num = neg_num + 1 if neg_num else 0
                pos_num += 1
            else:
                cur_pos = pos_num
                pos_num = neg_num + 1 if neg_num else 0
                neg_num = cur_pos + 1
            res = max(res, pos_num)
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        def helper(arr):
            inds = []
            for i,num in enumerate(arr):
                if num<0:
                    inds.append(i)
            if len(inds)%2==0:
                return len(arr)
            else:
                first = max(inds[0],len(arr)-inds[0]-1)
                second = max(inds[-1],len(arr)-inds[-1]-1)
                return max(first,second)
                
            
        temp = []
        for i,num in enumerate(nums):
            if num==0:
                temp.append(i)
        pos = []
        if temp:
            if nums[:temp[0]]:
                pos.append(nums[:temp[0]])
            for i in range(0,len(temp)-1):
                pos.append(nums[temp[i]+1:temp[i+1]])
            if nums[temp[-1]+1:]:
                pos.append(nums[temp[-1]+1:])
        else:
            pos.append(nums)
        ans = 0
        for arr in pos:
            ans = max(ans,helper(arr))
        return ans
            


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        lists = [[]]
        negative = [[]]
        index = 0
        for num in nums:
            if num == 0:
                index = 0
                negative.append([])
                lists.append([])
            else:
                if num < 0:
                    negative[-1].append(index)
                lists[-1].append(num)
                index += 1

        max_len = 0
        for l, neg in zip(lists, negative):
            if len(neg) % 2 == 1:
                dist = min(neg[0] + 1, len(l) - neg[-1])
            else:
                dist = 0
            max_len = max(len(l) - dist, max_len)
        
        return max_len


import copy
import math
class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        positive,negative = 0,0
        length = 0
        for n in nums:
            if  n == 0:
                positive,negative = 0,0
            elif n > 0:
                if negative > 0 : positive,negative = positive+1,negative+1
                else: positive,negative = positive+1,0
            else:
                if negative > 0 : positive,negative = negative+1,positive+1
                else: positive,negative = 0,positive+1
            length = max(length,positive)
        return length

import numpy as np
class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        if len(nums)==0: return (0)
        if len(nums)==1:return( 1 if nums[0]>0 else 0)
        St=[i for i,j in enumerate(nums) if (i==0 and j!=0) or (nums[i-1]==0 and j!=0)]
        if len(St)==0: return (0)
        Ed=[i for i,j in enumerate(nums) if (i==len(nums)-1 and j!=0) or (i<len(nums)-1 and nums[i+1]==0 and j!=0)]
        # print(St,Ed)
        Sta=np.array(St)
        Eda=np.array(Ed)
        Lns=(-(Eda-Sta+1)).argsort()
        # print(Lns)
        k=0
        mxLen=0
        while(k<len(Lns)):
            nums1=nums[St[Lns[k]]:(Ed[Lns[k]]+1)]
            if len(nums1)==mxLen: return(mxLen)
            ni=[i for i,j in enumerate(nums1) if j<0]
            if len(ni)==0 or len(ni)%2==0:mxLen=max(mxLen,len(nums1))
            else:
                mn=min(ni)
                mx=max(ni)
                mxLen= max(mxLen,mn,len(nums1)-mn-1,mx,len(nums1)-mx-1)
            k=k+1
        return(mxLen)


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        p = 1
        j = None
        k = -1
        m = 0
        for i, n in enumerate(nums):
            if not n:
                p = 1
                j = None
                k = i
            else:
                if n < 0:
                    p *= -1
                elif not n:
                    p = 0
                if p > 0:
                    m = max(m, i-k)
                elif p < 0:
                    if j is None:
                        j = i
                    else:
                        m = max(m, i-j)
        return m


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        # DP may be unnecessary, but because I saw max length subarray
        # I assumed that it would be DP. Solution approach was DP-esque
        # but it doesn't seem necessary.
        # Seems like another way could be to just count the number of
        # negatives (between 0s).
        p = 0
        n = 0
        longest_p = 0
        for num in nums:
            longest_p = max(longest_p, p)
            if num == 0:
                p = 0
                n = 0
            elif num > 0:
                prev_p = p
                prev_n = n
                p = prev_p + 1
                if prev_n > 0:
                    n = prev_n + 1
                else:
                    n = 0
            elif num < 0:
                prev_p = p
                prev_n = n
                n = prev_p + 1
                if prev_n > 0:
                    p = prev_n + 1
                else:
                    p = 0
        longest_p = max(longest_p, p)
        return longest_p


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 1 if nums[0] > 0 else 0 
        p1 = p2 = 0
        answer = 0
        curr_len = 0 
        neg_indx = deque([])
        while p2 < n:
            num = nums[p2]
            if num == 0:
                answer = max(answer, curr_len)
                curr_len = 0 
                p2 += 1
                p1 = p2 
                neg_indx = deque([])
            elif num > 0:
                curr_len += 1 
                answer = max(answer, curr_len) 
                p2 += 1 
            else:
                neg_indx.append(p2)
                j = p2+1
                found = False
                while j < n:
                    num2 = nums[j]
                    if num2 <= 0:
                        if num2 < 0:
                            neg_indx.append(j)
                            found = True 
                        break
                    j += 1 
                if found:
                    curr_len += (j-p2+1)
                    answer = max(answer, curr_len)
                    if j == n-1:
                        return answer 
                    else:
                        p2 = j + 1 
                else: 
                    first_neg = neg_indx.popleft()
                    while p1 <= first_neg:
                        p1 += 1
                        curr_len -= 1
                    if p1 > p2:
                        p2 = p1
                        answer = max(answer, curr_len)
                        curr_len = 0 
                    else:
                        curr_len += 1
                        p2 += 1
                    continue  
        return answer 
    
    
#[1, -4, 3, 2, 0, 2, -2, 3, -2, -2, 3, 4, 5]


class Solution:
    def getMaxLen(self, nums):
        
        if len(nums) == 0:
            return True
        
        result = 0
        count = 0
        zero_marker = -1
        negative_marker = -1
       
        for i in range(len(nums)):
            if nums[i] == 0:
                zero_marker = i
                count = 0
                negative_marker = -1
                

            else:
                if nums[i] < 0:
                    count += 1
                    if negative_marker == -1:
                        negative_marker = i
            
                if count % 2 == 0:
                    result = max(result, i - zero_marker)
                else:
                    result = max(result, i - negative_marker)
        return result      

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        neg = pos = res = 0
        for n in nums:
            if n == 0:
                neg = pos = 0
            elif n > 0:
                if neg:
                    neg += 1
                pos += 1
            else:
                pos, neg = neg + 1 if neg else 0, pos + 1
            res = max(res, pos)
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        def get_val(nums):
            # print(nums)
            if len(nums) == 0:
                return 0
            products = [1]
            product = 1
            length = len(nums)
            for i in range(length):
                product *= nums[i]
                products.append(product)
            for j in range(length, 0, -1):
                for k in range(length-j+1):
                    value = products[k+j]//products[k]
                    if value>0:
                        return j
            return 0
        index = 0
        maximum = 0
        for i in range(n):
            if nums[i] == 0:
                if i == index:
                    index += 1
                    continue
                value = get_val(nums[index:i])
                if value>maximum:
                    maximum = value
                index = i+1
            elif nums[i]>0:
                nums[i] = 1
            else:
                nums[i] = -1
        value = get_val(nums[index:n])
        if value>maximum:
            maximum = value
        return maximum

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        maxl = 0
        pos = 0
        neg = 0
        for n in nums:
            if n == 0:
                pos, neg = 0, 0
            elif n > 0:
                pos += 1
                neg = neg + 1 if neg != 0 else 0
            elif n < 0:
                oldneg = neg
                neg = pos + 1
                pos = oldneg + 1 if oldneg > 0 else 0
            maxl = max(maxl, pos)
        
        return maxl
                


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        def oddMinus(ls):
            ret = 0
            for i in range(len(ls)):
                if ls[i] < 0:
                    ret = max(max(ret, i), len(ls)-1-i)
            return ret
        
        def getLen(ls):
            minus = 0
            for i in ls:
                if i < 0:
                    minus += 1
            if(minus % 2 == 0):
                return len(ls)
            else:
                return oddMinus(ls)
        
        
        s = []
        sub = []
        for i in nums:
            if i == 0:
                s.append(sub)
                sub = []
            else:
                sub.append(i)
        s.append(sub)
        
        res = 0
        
        for ls in s:
            res = max(res, getLen(ls))
            
        return res


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        l = []
        neg = []
        index = 0
        max_len = 0
        for num in nums:
            if num == 0:
                index = 0
                if len(neg) % 2 == 1:
                    dist = min(neg[0] + 1, len(l) - neg[-1])
                else:
                    dist = 0
                max_len = max(len(l) - dist, max_len)
                l.clear()
                neg.clear()
            else:
                if num < 0:
                    neg.append(index)
                l.append(num)
                index += 1
        
        if len(neg) % 2 == 1:
            dist = min(neg[0] + 1, len(l) - neg[-1])
        else:
            dist = 0
        max_len = max(len(l) - dist, max_len)

        return max_len

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:

        n = len(nums)
        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 getMaxLen(self, nums: List[int]) -> int:
        ret = 0
        pos, neg = -1, None
        curr = 0
        for i, n in enumerate(nums):
            if n == 0:
                pos, neg = i, None
                curr = 0
            else:
                if n < 0:
                    curr = 1 - curr
            
                if curr == 0:    
                    ret = max(ret, i - pos)
                
                if curr == 1:
                    if neg is not None:
                        ret = max(ret, i - neg)
                    else:
                        neg = i
        return ret

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        nums.append(0)
        start = -1
        i = 0
        firstn = -1
        maxl = 0
        nneg = 0
        while i<len(nums):
            if nums[i]<0:
                nneg += 1
                if firstn<0: firstn = i
                lastn = i
            elif nums[i] == 0:
                if nneg%2 == 0:
                    maxl = max(maxl,i-start-1)
                else:
                    maxl = max([maxl,lastn-start-1,i-firstn-1])
                start = i
                nneg = 0
                firstn = -1
            i += 1
        return maxl

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        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 getMaxLen(self, nums: List[int]) -> int:
        def dfs(start):
            i = start
            if i >= len(nums):
                return 0
            ret = 0
            stack = []
            while i < len(nums):
                if nums[i] == 0:
                    break
                elif nums[i] < 0:
                    stack.append(i)
                i+=1
            if len(stack) % 2 == 0:
                ret = i - start
            else:
                ret = max(i-1-stack[0],stack[-1]-start)
            
            return max(ret,dfs(i+1))
        return dfs(0)
                    


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        def solve(arr):
            maxy = 0
            count = 0
            for i in j:
                if i < 0:
                    count += 1
            if count % 2 == 0:
                maxy = max(maxy,len(j))
            else:
                for i in range(len(j)):
                    if j[i] < 0:
                        m1 = i 
                        m2 = len(j) - m1 -1 
                        m3 = max(m1,m2)
                        maxy = max(maxy,m3)
                        break
                for i in range(len(j)-1,-1,-1):
                    if j[i] < 0:
                        m1 = i 
                        m2 = len(j) - m1 - 1 
                        m3 = max(m1,m2)
                        maxy = max(maxy,m3)
                        break
            return maxy
        res = []
        maxy = 0
        flag = 1
        i = 0
        for j in range(i,len(nums)):
            if nums[j] == 0:
                res.append(nums[i:j])
                i = j+1
                flag = 0
        if flag == 1:
            res.append(nums)
        elif flag == 0:
            res.append(nums[i:])
        nums = res
        for j in nums:
            maxy = max(maxy,solve(j))
        return maxy


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        firstNeg = -1
        zeroPos = -1
        cnt = 0
        ret = 0
        for i, n in enumerate(nums):
            if n < 0:
                cnt += 1
                if firstNeg == -1:
                    firstNeg = i
            elif not n:
                firstNeg, cnt = -1, 0
                zeroPos = i
            if cnt % 2:
                ret = max(ret, i - firstNeg)
            else:
                ret = max(ret, i - zeroPos)
        return ret


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        pos = neg = max_len = 0
        
        for n in nums:
            if n > 0:
                neg = (1 + neg) if neg > 0 else 0
                pos = (1 + pos)                
            elif n < 0:
                #n1 = neg
                #neg = (1 + pos)
                pos, neg = (1 + neg) if neg > 0 else 0, 1+pos
                 
            else:
                pos = neg = 0

                
            max_len = max(max_len, pos)
        return max_len


class Solution:
    def getMaxLen(self, arr: List[int]) -> int:
        i=0
        while i<=len(arr)-1 and arr[i]==0:
            i+=1
        arr=arr[i:]
        if len(arr)==0:
            return 0
        i=len(arr)-1
        while i<=len(arr)-1 and arr[i]==0:
            i-=1
        arr=arr[:i+1]
        if len(arr)==0:
            return 0
        array=[]
        low=0
        high=0
        ans=[]
        while low <len(arr):
            while  high<len(arr) and arr[high] != 0:
                high+=1
            if high == len(arr)-1:
                break
            else:
                array.append(arr[low:high])
                while high<len(arr) and arr[high]==0:
                    high+=1
                low=high
        for a in array:
            if len(a)==0:
                continue
            else:
                total=0
                first=0
                last=0
                for i in range(len(a)):
                    if a[i]<0:
                        total+=1
                if total%2==0:
                    ans.append(len(a))
                else:
                    i=0
                    while a[i]>0:
                        i+=1
                    first=len(a)-(i+1)
                    i=len(a)-1
                    while a[i]>0:
                        i-=1
                    last=i
                    
                ans.append(max(first,last))
        ma=0
        for i in ans:
            if i>ma:
                ma=i
        return ma


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        out = 0
        first = -1
        last = -1
        negs = 0
        start = 0
        for i,num in enumerate(nums):
            if num == 0:
                if negs % 2 == 0:
                    new_max = i-start
                else:
                    new_max = max(i-first-1,last-start)
                out = max(out,new_max)
                first = -1
                last = -1
                negs = 0
                start = i+1
            if num < 0:
                negs += 1
                if first == -1:
                    first = i
                last = i
        i+=1
        if negs % 2 == 0:
            new_max = i-start
        else:
            new_max = max(i-first-1,last-start)
        out = max(out,new_max)
        return out

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        dp = [[0 for i in range(2)]  for j in  range(len(nums) + 1)]
        res = 0
        for i, num in enumerate(nums):
            if num == 0:
                dp[i + 1][0] = dp[num][1] = 0
            elif num > 0:
                dp[i + 1][0] = dp[i][0] + 1
                dp[i + 1][1] = dp[i][1] + 1 if dp[i][1] else 0
            else:
                dp[i + 1][0] = dp[i][1] + 1 if dp[i][1] else 0
                dp[i + 1][1] = dp[i][0] + 1
            res = max(res, dp[i + 1][0])
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        ans = 0
        neg = 0
        lo, hi = 0, -1
        for i, num in enumerate(nums):
            if num == 0:
                lo = i+1
                neg = 0
            elif num < 0:
                neg += 1
            hi = i
            if neg % 2 == 0:
                #print(lo,hi)
                ans = max(ans, hi - lo + 1)
                
        neg = 0
        nums = nums[::-1]
        lo, hi = 0, -1
        for i, num in enumerate(nums):
            if num == 0:
                lo = i+1
                neg = 0
            elif num < 0:
                neg += 1
            hi = i
            if neg % 2 == 0:
                #print(lo,hi)
                ans = max(ans, hi - lo + 1)        

        return ans         


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        dp = [0 for _ in range(2)]
        res = 0
        
        if nums[0] > 0:
            dp[0] = 1
            res = 1
        if nums[0] < 0:
            dp[1] = 1
            
        
        for i in range(1, len(nums)):
            cur = nums[i]
            tmp = [0 for _ in range(2)]
            if cur > 0:
                tmp[0] = dp[0] + 1
                if dp[1] > 0:
                    tmp[1] = dp[1] + 1
            
            if cur < 0:
                tmp[1] = dp[0] + 1
                if dp[1] > 0:
                    tmp[0] = dp[1] + 1
            
            res = max(res, tmp[0])
            dp = tmp
        
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        positives = 0
        negatives = 0
        output = 0

        for i in range(len(nums)):
            if nums[i] > 0:
                positives += 1

                if negatives > 0:
                    negatives += 1

            elif nums[i] < 0:
                if negatives > 0:
                    tmp = positives
                    positives = negatives + 1 
                    negatives = tmp + 1 

                else:
                    negatives = positives + 1
                    positives = 0

            else:
                positives = 0
                negatives = 0

            output = max(output, positives)

        return output


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        neg = pos = 0
        ret = 0
        end = start = 0
        while end < len(nums):
            start = end
            while end < len(nums) and nums[end]:
                if nums[end] < 0:
                    neg += 1
                if nums[end] > 0:
                    pos += 1
                if neg % 2 == 0:
                    ret = max(ret, end - start + 1)
                    print(ret)
                end += 1
            while neg % 2:
                if nums[start] < 0:
                    neg -= 1
                    ret = max(ret, end - start - 1)
                start += 1
            neg = pos = 0
            while end < len(nums) and nums[end] == 0:
                end += 1
        return ret


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        pos_l = 0
        neg_l = 0
        best = 0
        
        for n in nums:
            if n == 0:
                pos_l = 0
                neg_l = 0
            elif n > 0:
                pos_l += 1
                if neg_l > 0:
                    neg_l += 1
            else:
                if neg_l == 0 and pos_l == 0:
                    neg_l = 1
                elif neg_l > 0 and pos_l > 0:                  
                    pos_l, neg_l = neg_l+1, pos_l+1        
                elif neg_l > 0:
                    pos_l = neg_l+1
                    neg_l = 1
                elif pos_l > 0:
                    neg_l = pos_l+1
                    pos_l = 0
            #print(n, pos_l, neg_l)
            best = max(best, pos_l)
        return best


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        cn=0;cp=0;f=0;n=len(nums);pz=-1;ans=0
        for i in range(n):
            if(nums[i]<0):
                if(f==0):fn=ln=i
                else:ln=i
                cn+=1;f=1
            elif(nums[i]>0):cp+=1
            else:
                if(cn%2==0):ans=max(ans,cn+cp)
                else:
                    z=cn+cp-min(i-ln,fn-pz)
                    ans=max(ans,z)
                f=0;cn=0;cp=0;pz=i
        if(cn%2==0):ans=max(ans,cn+cp)
        else:
            z=cn+cp-min(n-ln,fn-pz)
            ans=max(ans,z)
        return ans
        


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        pos = 0
        neg = 0
        max_pos = 0
        curr = True
        for i in range(len(nums)):
            # print(nums[i])
            
            if nums[i] > 0:
                pos += 1
                if neg != 0:
                    neg += 1                    
            
            elif nums[i] < 0:
                old_pos = pos
                if neg != 0:
                    pos = neg + 1
                else:
                    pos = 0
                neg = old_pos + 1
                
            
            else:
                neg = 0
                pos = 0


            max_pos = max(pos, max_pos)
            # print(pos, max_pos,neg)
        
        return max_pos

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        n = len(nums)
        
        pos, neg = [0] * len(nums), [0] * len(nums)
        
        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] = pos[i-1] + 1 
                neg[i] = 1 + neg[i-1] if neg[i-1] else 0
            
            elif nums[i] < 0:
                neg[i] = pos[i-1] + 1 
                pos[i] = 1 + neg[i-1] if neg[i-1] else 0 

            ans = max(ans, pos[i])
            
            
                
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        dp_pos = [0] * (len(nums) + 1)
        dp_neg = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            if(nums[i] > 0):
                dp_pos[i+1] = dp_pos[i] + 1
                if(dp_neg[i] == 0):
                    dp_neg[i+1] = 0
                else:
                    dp_neg[i+1] = dp_neg[i] + 1
            elif(nums[i] < 0):
                dp_neg[i+1] = dp_pos[i] + 1
                if(dp_neg[i] == 0):
                    dp_pos[i+1] = 0
                else:
                    dp_pos[i+1] = dp_neg[i] + 1
        return max(dp_pos)
        


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        from collections import defaultdict
        nums1 = []
        for i in nums:
            if i > 0:
                nums1.append(1)
            elif i < 0:
                nums1.append(-1)
            else:
                nums1.append(0)
        pre_arr = [0]*len(nums1)
        rem = []
        for i in range(len(nums1)):
            if i == 0:
                pre_arr[i] = nums1[i]
            else:
                if pre_arr[i-1] != 0:
                    pre_arr[i] = nums1[i]*pre_arr[i-1]
                else:
                    pre_arr[i] = nums1[i]
        a1 = max(nums)
        if a1 > 0:
            m1 = 1
        else:
            m1 = 0
        Dict = defaultdict(int)
        start = 0
        for i in range(len(pre_arr)):
            if pre_arr[i] > 0:
                m1 = max(m1, i - Dict[1]+1)
            elif pre_arr[i] == 0:
                Dict[1] = i+1
        # print(pre_arr)
        Dict1 = defaultdict(list)
        m2 = 0
        for i in range(len(pre_arr)):
            if pre_arr[i] < 0:
                Dict1[-1].append(i)
            elif pre_arr[i] == 0:
                if len(Dict1[-1]) >= 2:
                    m2 = max(m2, Dict1[-1][-1]-Dict1[-1][0])
                Dict1.clear()
        if len(Dict1[-1]) >= 2:
            m2 = max(m2, Dict1[-1][-1]-Dict1[-1][0])
        #print(m1, m2)
        return max(m1,m2)


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        pos = neg = max_len = 0
        
        for n in nums:
            if n > 0:
                neg, pos = (1 + neg) if neg > 0 else 0, 1+pos
                #pos = (1 + pos)                
            elif n < 0:
                #n1 = neg
                #neg = (1 + pos)
                pos, neg = (1 + neg) if neg > 0 else 0, 1+pos
                 
            else:
                pos = neg = 0

                
            max_len = max(max_len, pos)
        return max_len


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        pos = [0] * len(nums)
        neg = [0] * len(nums)
        
        pos[0] = 1 if nums[0] > 0 else 0
        neg[0] = 1 if nums[0] < 0 else 0
        
        for i in range(1, len(nums)):
            if nums[i] < 0:
                pos[i] = 1 + neg[i-1] if neg[i-1] > 0 else 0
                neg[i] = 1 + pos[i-1]
            elif nums[i] > 0:
                pos[i] = 1 + pos[i-1]
                neg[i] = 1 + neg[i-1] if neg[i-1] > 0 else 0
            else:
                pos[i] = 0
                neg[i] = 0
        return max(pos)
        
'''
pos[i] = max length subarray ending at i whose product is positive
neg[i] = max length subarray ending at i whose product is negative


pos[i] = (
    1 + pos[i-1], if nums[i] > 0
    1 + neg[i-1] elif nums[i] < 0
    0            else
)

neg[i] = (
    1 + neg[i-1], if nums[i] > 0
    1 + pos[i-1], elif nums[i] < 0
    0             else
)

A = [-1,-2,-3,0,1]
p = [0,  2, 2,]
n = [1,  1, 3]



[0,1,-2,-3,-4]

[0,1,0,3,2]
[0,0,2,1,]




'''

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        prod = 1
        p_start = -1
        n_start = 10 ** 6
        for i in range(n):
            if nums[i] == 0:
                p_start = i
                n_start = 10 ** 6
                prod = 1
                continue
            elif nums[i] < 0:
                prod = -prod
                if n_start == 10 ** 6:
                    n_start = i
            res = max(res, i - p_start) if prod > 0 else max(res, i - n_start)
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        neg = pos = max_len = 0
        fneg = lneg = -1
        beg = -1
        
        for i, n in enumerate(nums):
            if n < 0:
                neg += 1
                if fneg == -1:
                    fneg = lneg = i
                else:
                    lneg = i
            elif n > 0:
                pos += 1
            else:
                if neg%2 == 0:
                    max_len = max(max_len, neg+pos)
                else:                    
                    max_len = max(max_len, max(lneg - beg - 1, i - fneg - 1))
                    print((i, fneg, lneg, beg))
                neg = pos = 0
                fneg = lneg = -1
                beg = i
                
        if neg%2 == 0:
            max_len = max(max_len, neg+pos)
        else:
            max_len = max(max_len, max(i - fneg, lneg - beg - 1))

        return max_len


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        l = len(nums)
        dp = [[0 for _ in range(2)] for _ in range(l)]
        res = 0
        if nums[0] > 0:
            dp[0][0] = 1
            res = 1
        if nums[0] < 0:
            dp[0][1] = 1
        
        for i in range(1, len(nums)):
            cur = nums[i]
            if cur > 0:
                if dp[i-1][0] == 0:
                    dp[i][0] = 1
                else:
                    dp[i][0] = dp[i-1][0] + 1
                
                if dp[i-1][1] != 0:
                    dp[i][1] = dp[i-1][1] + 1
                    
            if cur < 0:
                if dp[i-1][0] == 0:
                    dp[i][1] = 1
                else:
                    dp[i][1] = dp[i-1][0] + 1
                
                if dp[i-1][1] != 0:
                    dp[i][0] = dp[i-1][1] + 1
            
            res = max(res, dp[i][0])
        
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        v = {(0,0):-1}
        neg = 0
        zero = 0
        maxlen = 0
        for i,num in enumerate(nums):
            if num < 0:
                neg = 1 - neg
            if num == 0:
                zero += 1
            if (neg,zero) not in v:
                v[(neg,zero)] = i
            else:
                maxlen = max(maxlen,i-v[(neg,zero)])
        # print(v)
        return maxlen
                


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        res = 0
        dp_po, dp_ne = [0] * (len(nums) + 1), [0] * (len(nums) + 1)
        
        for i, value in enumerate(nums):
            if value == 0:
                dp_po[i + 1] = 0
                dp_ne[i + 1] = 0
            elif value > 0:
                dp_po[i + 1] = dp_po[i] + 1
                if dp_ne[i] > 0:
                    dp_ne[i + 1] = dp_ne[i] + 1
            else:
                dp_ne[i + 1] = dp_po[i] + 1
                if dp_ne[i] > 0:
                    dp_po[i + 1] = dp_ne[i] + 1
            if dp_po[i + 1] > res:
                res = dp_po[i + 1]
        
        return res


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        fn=-1
        zi=-1
        cn=0
        dig=0
        maxdig=0
        for i in range(len(nums)):
            if(nums[i]<0):
                cn+=1
                if(fn==-1):
                    fn=i
            if(nums[i]==0):
                fn=-1
                cn=0
                zi=i
            else:
                if(cn%2==0):
                    maxdig=max(i-zi,maxdig)
                else:
                    maxdig=max(i-fn,maxdig)
        return maxdig

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        res = 0
        n = len(nums)
        
        non_zeros = []
        i = 0
        pre = 0
        while i < n:
            if nums[i] == 0:
                if i > pre:
                    non_zeros.append(nums[pre:i])
                pre = i + 1
            i += 1
        if i > pre:
            non_zeros.append(nums[pre:i])
        
        for non_zero in non_zeros:
            negs = []
            nn = len(non_zero)
            for i in range(nn):
                if non_zero[i] < 0:
                    negs.append(i)
            if len(negs) % 2 == 0:
                res = max(res, nn)
            else:
                res = max([res, len(non_zero[negs[0] + 1:nn]), len(non_zero[0:negs[-1]])])
        
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n=len(nums)
        i=0
        ans=float('-inf')
        while i<n:
            s=i
        
            while s<n and nums[s]==0:
                s+=1
            e=s
            c=0
            sn=-1
            en=-1
            while e<n and nums[e]!=0:
                if nums[e]<0:
                    c+=1
                    if sn==-1:
                        sn=e
                    en=e
                e+=1
            if c%2==0:
                ans=max(ans,e-s)
            else:
                if sn!=-1:
                    ans=max(ans,e-sn-1)
                if en!=-1:
                    ans=max(ans,en-s)
            i=e+1
        return ans
                    
            
       
            


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        pos, neg = 0, 0
        res = 0
        for n in nums:
            if n==0:
                neg, pos = 0, 0
            elif n>0:
                if neg>0: neg, pos = neg+1, pos+1
                else: neg, pos = 0, pos+1
            else:
                if neg>0: pos, neg = neg+1, pos+1
                else: neg, pos = pos+1, 0
            res = max(res,pos)
        return res




class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        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 getMaxLen(self, nums: List[int]) -> int:
        p = 1
        j = None
        k = -1
        m = 0
        for i, n in enumerate(nums):
            if not n:
                p = 1
                j = None
                k = i
            else:
                if n < 0:
                    p = -p
                if p > 0:
                    m = max(m, i-k)
                elif p < 0:
                    if j is None:
                        j = i
                    else:
                        m = max(m, i-j)
        return m


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        # if the number of negative numbers is even then we just need to worry about zeroes
        maxLength = 0
        currLength = 0
        negCnt = 0
        negIdxs = []
        head = 0
        for i, n in enumerate(nums):
            if n > 0:
                currLength += 1
                if negCnt%2 == 0:
                    maxLength = max(maxLength, currLength)
            elif n < 0:
                currLength += 1
                negCnt += 1
                negIdxs.append(i)
                if negCnt%2 == 0:
                    maxLength = max(maxLength, currLength)
            if n == 0 or i == len(nums) - 1: # end or 0
                # head and tail?
                if negIdxs:
                    tail = i if n > 0 else i - 1
                    maxLength = max(maxLength, tail - negIdxs[0])
                    # print(negIdxs[-1], head)
                    maxLength = max(maxLength, negIdxs[-1] - head)
                currLength = 0
                negCnt = 0
                negIdxs = []
                head = i + 1
        return maxLength
        
        # negIdx = []
        # zeroIdx = []
        # for i, n in enumerate(nums):
        #     if n < 0:
        #         negIdx.append(i)
        #     elif n == 0:
        #         zeroIdx.append(i)
        # if len(negIdx)%2 == 0:
        #     if len(zeroIdx) == 0:
        #         return len(nums)
        #     else:
        #         for 
        # else:


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        # \"pos\", \"neg\" represent longest consecutive numbers ending with nums[i] forming a positive/negative product.
        nums.append(0)
        n = len(nums)
        pos, neg = 0, 0
        if nums[0] > 0: pos = 1
        if nums[0] < 0: neg = 1
        ans = pos
        for i in range(1, n):
            if nums[i] > 0:
                pos = 1 + pos
                neg = 1 + neg if neg > 0 else 0
            elif nums[i] < 0:
                pre_pos, pre_neg = pos, neg
                pos = 1 + pre_neg if pre_neg > 0 else 0
                neg = 1 + pre_pos
            else:
                pos, neg = 0, 0
            ans = max(ans, pos)
        return ans
    
        # nums.append(0)
        # start = -1
        # i = 0
        # firstn = -1
        # maxl = 0
        # nneg = 0
        # while i<len(nums):
        #     if nums[i]<0:
        #         nneg += 1
        #         if firstn<0: firstn = i
        #         lastn = i
        #     elif nums[i] == 0:
        #         if nneg%2 == 0:
        #             maxl = max(maxl,i-start-1)
        #         else:
        #             maxl = max([maxl,lastn-start-1,i-firstn-1])
        #         start = i
        #         nneg = 0
        #         firstn = -1
        #     i += 1
        # return maxl


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        n=len(nums)
        for i in range(n):
            if nums[i]>0:
                nums[i]=1
            elif nums[i]<0:
                nums[i]=-1
        
        # print(nums)
        ans=0
        old=1
        for i in range(n):
            # print(i)
            temp=i
            count=0
            j=i
            pro=1
            old=1
            while j<n:
                
                pro=pro*nums[j]
                # print(pro,end=' ')                
                if pro==0:
                    # print(\" \")
                    i=j+1
                    break

                count+=1
                if pro>0:
                    if count>ans:
                        ans=count                
                j=j+1
                old=pro
                # print((count,old))
                # print(\" \")
            # print(\"TATTI\")    
            

            if pro==0 and old>0:
                if ans<count:
                    ans=count
            elif old<0:
                            
                left=1
                right=1
                for z in range(temp,j):
                    if nums[z]==-1:
                        break
                    left+=1
                z=j-1
                while z>=temp:
                    if nums[z]==-1:
                        break
                    right+=1
                    z=z-1
                q=min(left,right)
                # print((temp,j,q))
                # print((j-temp+1-q)-1)
                if (j-temp+1-q)-1>ans:
                    ans=(j-temp+1-q)-1
            # print('ans = '+str(ans))
            if j>=n:
                break
            
        return ans
                    
                


class Solution:
    def getMaxLen(self, nums: List[int], reverse=False) -> int:
        zero_pos = -1
        num_negative = 0
        first_negative = -1
        res = 0
        for i in range(len(nums)):
            if nums[i] < 0:
                num_negative += 1
                if first_negative == -1:
                    first_negative = i
            if nums[i] == 0:
                zero_pos = i
                num_negative = 0
                first_negative = -1
            if nums[i] > 0 or nums[i] < 0:
                if num_negative % 2 == 0:
                    res = max(res, i - zero_pos)
                else:
                    res = max(res, i - first_negative)
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        # \"pos[i]\", \"neg[i]\" represent longest consecutive numbers ending with nums[i] forming a positive/negative product.

        n = len(nums)
        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 getMaxLen(self, nums: List[int]) -> int:
        ans = pos = neg = 0
        for x in nums: 
            if x > 0: pos, neg = 1 + pos, 1 + neg if neg else 0     # assignment in one line is very important to have the previous value of variables updated! Cannot be re-written into 2 lines!
            elif x < 0: pos, neg = 1 + neg if neg else 0, 1 + pos
            else: pos = neg = 0 # reset 
            ans = max(ans, pos)
        return ans 


def f(data):
    n2 = len(data)
    
    f0 = -1
    f1 = -1
    n = 0
    for ind,d in enumerate(data):
        if d==1:
            continue
        n += 1
        if f0==-1:
            f0 = ind
        f1 = ind
            
    if n&1==0:
        return n2
    
    return max(f1, n2-f0-1)

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        res = 0
        prev = -1
        data = []
        for ind,num in enumerate(nums):
            if num==0:
                if data:
                    res = max(res, f(data))
                prev = ind
                data = []
                continue
                
            data.append(1 if num>0 else -1)
            
        res = max(res, f(data))
        return res
                
            
        


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        res = 0
        pos, neg = set(), set()
        for num in nums:
            if num > 0:
                pos = {x+1 for x in pos} | {1}
                neg = {y+1 for y in neg}
            elif num < 0:
                pos = {x+1 for x in pos} | {1}
                neg = {y+1 for y in neg}       
                pos, neg = neg, pos
            else:
                pos, neg = set(), set()
            
            if len(pos):
                res = max(res, max(pos))
            # print(res)
            
            if len(pos): pos = set([max(pos)])
            if len(neg): neg = set([max(neg)])
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        max_pos = 0
        max_neg = 0
        max_len = 0
        for n in nums:
            if n == 0:
                max_pos = max_neg = 0
            elif n > 0:
                max_pos += 1
                if max_neg:
                    max_neg += 1
            else:
                prev_pos = max_pos
                if max_neg:
                    max_pos = max_neg + 1
                else:
                    max_pos = 0
                max_neg = prev_pos + 1
            max_len = max(max_len, max_pos)
        return max_len

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        max_length = 0
        
        idx = 0
        prev = 0
        negative = 0
        while idx < len(nums):
            num = nums[idx]
            if num == 0:
                prev = 0
                negative = 0
            elif num < 0:
                if negative == 1:
                    prev = neg_idx + (idx-prev_neg_idx) + 1 
                    negative = 0
                else:
                    prev_neg_idx = idx
                    neg_idx = prev
                    negative = 1
            else:
                if prev == 0 or negative == 0:
                    prev += 1
            #print(prev)
            max_length = max(max_length, prev)
            idx += 1
            
        idx = len(nums)-1
        prev = 0
        negative = 0
        while idx >= 0:
            num = nums[idx]
            if num == 0:
                prev = 0
                negative = 0
            elif num < 0:
                if negative == 1:
                    prev = neg_idx + (prev_neg_idx-idx) + 1 
                    negative = 0
                else:
                    prev_neg_idx = idx
                    neg_idx = prev
                    negative = 1
            else:
                if prev == 0 or negative == 0:
                    prev += 1
            #print(prev)
            max_length = max(max_length, prev)
            idx -= 1            

        return max_length
            


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        i_pos,i_neg=-1,len(nums)
        pro=1
        res=0
        for i in range(len(nums)):
            if nums[i]==0:
                i_pos,i_neg=i,len(nums)
                pro=1
            else: 
                if nums[i]<0: pro*=-1
      
                if pro>0:
                    i_pos=min(i,i_pos)
                    res=max(res,i-i_pos)
                else:
                    i_neg=min(i,i_neg)
                    res=max(res,i-i_neg)
        return res


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        max_pos_len = 0
        max_neg_len = 0
        if nums[0] > 0: max_pos_len = 1
        if nums[0] < 0: max_neg_len = 1
        max_len = max(0, max_pos_len)
        
        for i in range(1, len(nums)):
            if nums[i] > 0: 
                max_pos_len += 1
                max_neg_len += (max_neg_len > 0)
            elif nums[i] < 0: 
                max_neg_len, max_pos_len = max_pos_len+1, max_neg_len+(max_neg_len > 0)
            elif nums[i] == 0: 
                max_pos_len = max_neg_len = 0
            
            max_len = max(max_len, max_pos_len)
        
        return max_len


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        ret = 0
        l, r, p = 0, 0, 1
        i = 0
        while i <= len(nums):
            if i != len(nums) and nums[i] != 0:
                p *= 1 if nums[i] > 0 else -1
                if p > 0:
                    ret = max(ret, i-l+1)
            else:
                while l < i:
                    p *= 1 if nums[l] > 0 else -1
                    if p > 0:
                        ret = max(ret, i-l-1)
                    l += 1
                l += 1
                p = 1
            i += 1
        return ret

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            if nums[i] > 0:
                nums[i] = 2
            elif nums[i] < 0:
                nums[i] = -2
        mini, maxi, res = 1, 1, -10**9 - 1
        for n in nums:
            a = mini * n
            b = maxi * n
            mini = min(a,b,n)
            maxi = max(a,b,n)
            res = max(res, maxi)
        if res <= 0:
            return 0
        return int(math.log2(res))


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        def getMaxLenHelper(nums: List[int]) -> int:
           ans = 0
           count,count1,negativeCount = 0,0,0
           for i in range(len(nums)):
              if nums[i] == 0:
                  if count > ans:
                     ans = count
                  count,count1,negativeCount = 0,0,0
              else:
                if nums[i] > 0:
                    count += 1
                count1 += 1
                if nums[i] < 0:
                   negativeCount += 1
                   if negativeCount == 2:
                      count = count1
                      negativeCount = 0
                   else:
                      if count > ans:
                         ans = count
                      count = 0
           if count > ans:
              ans = count
           return ans
        return max(getMaxLenHelper(nums),getMaxLenHelper(nums[::-1]))
        
            


class Solution:
    def getMaxLen(self, nums):
        n = len(nums)
        pos, neg = 0, 0
        res = 0
        for i in range(n):
            if nums[i] > 0:
                pos, neg = 1 + pos, 1 + neg if neg else 0
            elif nums[i] < 0:
                pos, neg = 1 + neg if neg else 0, 1 + pos
            else:
                pos, neg = 0, 0
            res = max(res, pos)
        return res  

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        N = len(nums)
        pos, neg = [0] * N, [0] * N
        if nums[0] > 0: pos[0] = 1
        if nums[0] < 0: neg[0] = 1
        res = pos[0]
        
        for i in range(1, N):
            if nums[i] > 0:
                pos[i] = pos[i - 1] + 1
                neg[i] = neg[i - 1] + 1 if neg[i - 1] > 0 else 0
            elif nums[i] < 0:
                pos[i] = neg[i - 1] + 1 if neg[i - 1] > 0 else 0
                neg[i] = pos[i - 1] + 1
            res = max(pos[i], res)
        return res


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        pos = int(nums[0] > 0)
        neg = int(nums[0] < 0)
        best = pos
        for i in nums[1:]:
            if i > 0:
                pos+= 1
                if neg > 0:                
                    neg += 1    
                else:
                    neg = 0
            elif i < 0:
                pTemp = pos
                if neg > 0:
                    pos = neg + 1
                else:
                    pos = 0
                neg = pTemp + 1
            else:
                pos,neg = 0,0
            best = max(best, pos)
        return best

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        # just count even number of negatives, no zeros though
        
        
        
        left = right = negCount = negIndex = res = 0
        
        while right <= len(nums):
            if right < len(nums) and nums[right] != 0:
                if nums[right] < 0:
                    negCount += 1
                    negIndex = right
                    
                right += 1                
            else:
                if negCount % 2 == 1:
                    res = max(res, negIndex - left)
                    while nums[left] > 0: left += 1
                        
                    res = max(res, right - left - 1)
                else:
                    res = max(res, right - left)
                
                right += 1
                left = right
                negCount = 0 
        
        return res
                
                


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        trip_zeros = []
        for num in nums:
            if num:
                if trip_zeros: trip_zeros[-1].append(num)
                else: trip_zeros.append([num])
            else:
                trip_zeros.append([])
        
        def count(arr):
            start = ans = 0
            left_neg = None
            pos = 1
            for end in range(len(arr)):
                if arr[end] < 0:
                    if left_neg is None:
                        left_neg = end
                    pos ^= 1
                print(pos, start, end, left_neg)
                if pos:
                    ans = max(ans, end-start+1)
                    
                else:
                    ans = max(ans, end-left_neg)
            return ans
        
        # print(trip_zeros)
        # if not trip_zeros: return 0
        return max(map(count, trip_zeros))

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        ans = 0
        last_zero = last_negative = -1
        running_count = 0
        negative_count = 0
        for i,v in enumerate(nums):
            if v == 0:
                last_zero = last_negative = i
                running_count = zero_count = negative_count = 0
            elif v < 0:
                negative_count += 1
                if negative_count == 1: last_negative = i
                if negative_count % 2 == 0: ans = max(ans,i-last_zero)
                else: ans = max(ans,i-last_negative)
            else:
                if negative_count % 2 == 0: ans = max(ans,i-last_zero)
                else: ans = max(ans,i-last_negative)
        return ans

class Solution:         
        
    def getMaxLenDuh(self, nums: List[int]) -> int:
        '''
        Single pass: at each num, track length of pos and neg prods:
            reset on 0, and change sign as needed.
        '''
        size = len(nums)
        if not size:
            return 0
        if size == 1:
            return 1 if nums[0] > 0 else 0
        
        
        result = nneg = npos = 0
        for num in nums:
            if num == 0:
                nneg = npos = 0     # reset
            elif num > 0:
                npos = npos + 1                 # any pos prod stays neg
                nneg = nneg + 1 if nneg else 0  # any neg prod stays neg
            else:
                temp = nneg
                nneg = npos + 1                 # any pos prod flips neg
                npos = temp + 1 if temp else 0  # any neg prod flips pos
            result = max(result, npos)          # Save max pos prod len
        return result
    

    def getMaxLenPow2(self, numso: List[int]) -> int:
        '''

        '''
        nums = [copysign(num, 2) for num in numso]
        size = len(nums)
        if size == 0:
            return
        left_prod, right_prod = 0, 0
        max_prod = -float('inf')
        for i in range(size):
            left_prod = (left_prod or 1) * nums[i]
            right_prod = (right_prod or 1) * nums[size - 1 - i]
            max_prod = max(max_prod, left_prod, right_prod)
        return math.log(max_prod, 2)

    
    def getMaxLen(self, nums: List[int]) -> int:
        '''

        '''
        return self.getMaxLenDuh(nums)


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        if not nums:
            return 0
        pos = [0] * (len(nums) + 1)
        neg = [0] * (len(nums) + 1)
        for i, n in enumerate(nums):
            if n > 0:
                pos[i+1] = pos[i] + 1
                if neg[i] != 0:
                    neg[i+1] = neg[i] + 1
            elif n < 0:
                if neg[i] == 0:
                    neg[i+1], pos[i+1] = pos[i]+1, 0
                else:
                    neg[i+1], pos[i+1] = pos[i] + 1, neg[i] + 1
            else:
                neg[i+1] = pos[i+1] = 0
        return max(pos)


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        max_count = 0
        front = 0
        back = 0
        prod = 1
        
        for i in range(len(nums)):
            if nums[i] > 0:
                nums[i] = 1
            elif nums[i] < 0:
                nums[i] = -1
        
        while back < len(nums):
            if nums[back] == 0:
                back -= 1
                while front <= back and front < len(nums):
                    if nums[front] != 0:
                        prod /= nums[front]
                        front += 1
                        if prod > 0:
                            max_count = max(max_count, back - front + 1)
                    else:
                        front += 1
                
                front += 1
                back = front
                
            else:
                prod *= nums[back]
                if prod > 0:
                    max_count = max(max_count, back - front + 1)
                back += 1
        
        back -= 1
        while front <= back and front < len(nums):
            if nums[front] != 0:
                prod /= nums[front]
                front += 1
                if prod > 0:
                    max_count = max(max_count, back - front + 1)
            else:
                front += 1

                    
        return max_count

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        if not nums:
            return 0

        dp = [[0, 0] for _ in range(len(nums))]
        dp[0] = [int(bool(nums[0] > 0)), int(bool(nums[0] < 0))] # max length (positive, negative)

        for idx in range(1, len(nums)):
            if nums[idx] == 0:
                continue
            if nums[idx] > 0:
                dp[idx][0] = dp[idx - 1][0] + 1
                dp[idx][1] = dp[idx - 1][1] + int(dp[idx - 1][1] != 0)
            else:
                dp[idx][0] = dp[idx - 1][1] + int(dp[idx - 1][1] != 0) 
                dp[idx][1] = dp[idx - 1][0] + 1

        return max([positive for positive, _ in dp])


class Solution:
    
    @staticmethod
    def process(st, end, cnt_neg, arr):
        if st >= 0 and st <= end and end >= 0:
            if not (cnt_neg % 2):
                return end - st + 1
            first_neg_ind = st 
            last_neg_ind = end
            while(first_neg_ind <= end and arr[first_neg_ind] >= 0):
                first_neg_ind += 1
            while(last_neg_ind >= st and arr[last_neg_ind] >= 0):
                last_neg_ind -= 1
            print((st, end, first_neg_ind, last_neg_ind))
            return max(last_neg_ind - st, end - first_neg_ind)
            
        return 0
    
    def getMaxLen(self, nums: List[int]) -> int:
        prev = 0
        ans = 0
        cnt_neg = 0
        for i in range(len(nums)):
            if not nums[i]:
                ans = max(ans, Solution.process(prev, i-1, cnt_neg, nums))
                prev = i + 1
                cnt_neg = 0
            if nums[i] < 0:
                cnt_neg += 1
        ans = max(ans, Solution.process(prev, len(nums)-1, cnt_neg, nums))
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        res = curr = 0
        dp = {0:0}
        for i,num in enumerate(nums,1):
            if num==0:
                curr = 0
                dp = {0:i}
                continue
            curr = (curr+(num<0))%2
            if curr not in dp:
                dp[curr]=i
            else:
                res = max(res,i-dp[curr])
        return res

import heapq
class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        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 getMaxLen(self, nums: List[int]) -> int:
        hashmap={0:-1}
        totalN=0
        ans=0
        for i in range(0,len(nums)):
            if nums[i]<0:
                totalN+=1
            
            value=totalN%2
            if nums[i]==0:
                hashmap={0:i}
                
                totalN=0
                continue
            if value in hashmap:
                ans=max(ans,i-hashmap[value])
            else:
                hashmap[value]=i
        return ans          

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        maxl = 0
        
        posi = None
        start = -1
        cur = True
        for i,n in enumerate(nums):
            if n == 0:
                start = i
                posi = None
                cur = True
                
            elif n > 0:
                if cur:
                    maxl = max(maxl,i-start)
                    
                else:
                    if posi == None:
                        maxl = max(maxl,1)
                        posi = i
                    else:
                        maxl = max(maxl,i-posi+1)
                 
                
            else:
                if not cur:
                    maxl = max(maxl,i-start)
                    if not posi:
                        posi = i
                    cur = True
                else:
                    cur = False
                     
                    if posi:                        
                        maxl = max(maxl,i-posi+1)
                 
        return maxl

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        n = len(nums)
        pos = [0]*n
        neg = [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] = pos[i-1] + 1
                neg[i] = neg[i-1] + 1 if neg[i-1] > 0 else 0
                
            elif nums[i] < 0:
                pos[i] = neg[i-1] + 1 if neg[i-1] > 0 else 0
                neg[i] = pos[i-1] + 1
            # else:
                # pos[i]
            ans = max(ans, pos[i])
        
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        i = 0
        j = 0
        minus = 0
        res = 0
        
        while j < len(nums):
            if nums[j] < 0:
                minus+=1
                j+=1
            elif nums[j] > 0:
                j+=1
            else:
                minus = 0
                i = j+1
                j = i
            if minus%2==0:
                res = max(res, j-i)
                
        
        if minus%2==0:
            res = max(res, j-i)
        
        minus = 0
        i = len(nums)-1
        j = len(nums)-1
        
        while j >= 0:
            if nums[j] < 0:
                minus+=1
                j-=1
            elif nums[j] > 0:
                j-=1
            else:
                minus = 0
                i = j-1
                j = i
            if minus%2==0:
                res = max(res, i-j)
                
        
        if minus%2==0:
            res = max(res, i-j)
            
        return res
            


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        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 getMaxLenDuh(self, nums: List[int]) -> int:
        '''
        Single pass: at each num, track length of pos and neg prods:
            reset on 0, and change sign as needed.
        '''
        size = len(nums)
        if not size:
            return 0
#         if size == 1:
#             return 1 if nums[0] > 0 else 0
        
        
        result = nneg = npos = 0
        for num in nums:
            if num == 0:
                nneg = npos = 0     # reset
            elif num > 0:
                npos = npos + 1                 # any pos prod stays neg
                nneg = nneg + 1 if nneg else 0  # any neg prod stays neg
            else:
                temp = nneg
                nneg = npos + 1                 # any pos prod flips neg
                npos = temp + 1 if temp else 0  # any neg prod flips pos
            result = max(result, npos)          # Save max pos prod len
        return result
    

    def getMaxLenPow2(self, numso: List[int]) -> int:
        '''

        '''
        nums = [copysign(num, 2) for num in numso]
        size = len(nums)
        if size == 0:
            return
        left_prod, right_prod = 0, 0
        max_prod = -float('inf')
        for i in range(size):
            left_prod = (left_prod or 1) * nums[i]
            right_prod = (right_prod or 1) * nums[size - 1 - i]
            max_prod = max(max_prod, left_prod, right_prod)
        return math.log(max_prod, 2)

    
    def getMaxLen(self, nums: List[int]) -> int:
        '''

        '''
        return self.getMaxLenDuh(nums)


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        '''
        f(i, 0) +
        f(i, 1) -
        f(i, 0) = max(f(i-1, 0)*nums[i]>0, f(i-1, 1), nums[i] < 0)
        f(i, 1) = 
        '''
        dp = defaultdict(int)
        for i, num in enumerate(nums):
            if num > 0: dp[(i, 0)] = 1
            if num < 0: dp[(i, 1)] = 1
        
        ans = dp[(0, 0)]
        for i in range(1, len(nums)):
            if nums[i] > 0:
                dp[(i, 0)] = max(dp[(i, 0)], dp[(i-1, 0)]+1 if dp[(i-1, 0)] > 0 else 0)
                dp[(i, 1)] = max(dp[(i, 1)], dp[(i-1, 1)]+1 if dp[(i-1, 1)] > 0 else 0)
            if nums[i] < 0:
                dp[(i, 0)] = max(dp[(i, 0)], dp[(i-1, 1)]+1 if dp[(i-1, 1)] > 0 else 0)
                dp[(i, 1)] = max(dp[(i, 1)], dp[(i-1, 0)]+1 if dp[(i-1, 0)] > 0 else 0)
            ans = max(ans, dp[(i, 0)])
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        neg = [0 for ii in range(len(nums))]
        zero = []
        if nums[0] < 0:
            neg[0] = 1
        elif nums[0] == 0:
            zero.append(0)

        for i in range(1, len(nums)):
            if nums[i] < 0:
                neg[i] = neg[i-1] + 1  
            else:
                neg[i] = neg[i-1]
            
            if nums[i] == 0:
                zero.append(i)

        l = 0
        ans = 0
        if len(zero) == 0:
            if neg[len(nums)-1] % 2 == 0:
                ans = max(ans, len(nums))
            else:
                first, last = -1, -1
                for i in range(len(nums)):
                    if nums[i] < 0:
                        last = i
                        if first == -1:
                            first = i
                ans = max(ans, last)
                ans = max(ans, len(nums)-first-1)
            
        for z in zero:
            if z == l:
                l = z+1
                continue
            else:
                if l == 0:
                    if neg[z-1] % 2 == 0:
                        ans = max(ans, z)
                    else:
                        first, last = -1, -1
                        for i in range(l, z):
                            if nums[i] < 0:
                                last = i
                                if first == -1:
                                    first = i
                        ans = max(ans, last)
                        ans = max(ans, z-first-1)
                else:
                    if (neg[z-1] - neg[l-1]) % 2 == 0:
                        ans = max(ans, z-l)
                    else:
                        first, last = -1, -1
                        for i in range(l, z):
                            if nums[i] < 0:
                                last = i
                                if first == -1:
                                    first = i
                        ans = max(ans, last-l)
                        ans = max(ans, z-first-1)
                l = z+1

        z = len(nums)
        if l == 0:
            if neg[z-1] % 2 == 0:
                ans = max(ans, z)
            else:
                first, last = -1, -1
                for i in range(l, z):
                    if nums[i] < 0:
                        last = i
                        if first == -1:
                            first = i
                ans = max(ans, last)
                ans = max(ans, z-first-1)
        else:
            if (neg[z-1] - neg[l-1]) % 2 == 0:
                ans = max(ans, z-l)
            else:
                first, last = -1, -1
                for i in range(l, z):
                    if nums[i] < 0:
                        last = i
                        if first == -1:
                            first = i
                ans = max(ans, last-l)
                ans = max(ans, z-first-1)
        return ans


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 1 if nums[0] > 0 else 0
        
        def find(start, end):
            if start+1 == end:
                return 0
            
            neg_count = sum(1 for x in range(start+1, end) if nums[x] < 0 ) 
            if neg_count % 2 == 0:
                return end-start+1-2
            
            first_neg, last_neg = None, None
            for idx in range(start+1, end):
                if nums[idx] < 0:
                    if first_neg is None:
                        first_neg = idx
                    last_neg = idx    
                    
            return max(last_neg-1-(start+1)+1, end-1-(first_neg+1)+1)
            
        
        NEG, POS, ZERO = -1, +1, 0
        nums = [0]+nums+[0]
        n = len(nums)
        
        start = 0
        end = 1
        ans = 0
        while end < n:
            while end < n and nums[end] != 0:
                end += 1
                
            ans = max(ans, find(start, end))
            start = end 
            end += 1
        return ans    
        
       #def get_type(n):
       #    nonlocal NEG, POS, ZERO
       #    
       #    if n > 0:
       #        return POS
       #    elif n < 0:
       #        return NEG
       #    else:
       #        return ZERO
       #    

       #arr = []
       #cur_type, cur_count = None, 0 
       #for n in nums:
       #    n_type = get_type(n)
       #    
       #    if n_type == cur_type:
       #        cur_count += 1
       #    else:    
       #        if cur_type is not None:
       #            arr.append(cur_type, cur_count)
       #        cur_count = 1
       #        cur_type = n_type
       #if cur_type is not None:
       #    arr.append(cur_type, cur_count)
       #    
       #for type, count in arr:
       #    if type == NEG and count % 2 == 0:
       #        
       #    
       #    
       #for type, count in arr:     


### I was thinking about prefix sum direction and try to figure out relationship between current number and previous number


### besides dynamic programming, is there another way of doing it?????


### good dynamic programming in here https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/discuss/819432/Python-Easy-to-understand-DP
# dp[i][0] : max length of subarray ending with index i With positive product   
# dp[i][1] : max length of subarray ending with index i With negative product 


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        dp = [[0,0] for _ in range(len(nums))]
        res = 0
        if nums[0] > 0:
            dp[0][0] = 1
        elif nums[0] < 0:
            dp[0][1] = 1
        #print(dp)
        res = max(res, dp[0][0])
        for idx in range(1, len(nums)):
            if nums[idx] == 0:
                dp[idx][0], dp[idx][1] = 0, 0
            elif nums[idx] > 0:
                dp[idx][0] = dp[idx-1][0] + 1
                if dp[idx-1][1] > 0:
                    dp[idx][1] = dp[idx-1][1] + 1
                res = max(dp[idx][0], res)
            
            elif nums[idx] < 0:
                dp[idx][1] = dp[idx-1][0]+1
                if dp[idx-1][1] > 0:
                    dp[idx][0] = dp[idx-1][1]+1
                res = max(res, dp[idx][0])
                
        #print(dp)
        return res



'''
class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        diction = {}
        diction[\"pos\"], diction[\"neg\"] = 0, 0
        prevpos, prevneg = 0, 0
        res = 0
        for num in nums:
            if num == 0:
                diction[\"pos\"], diction[\"neg\"] = 0, 0
                prevpos, prevneg = 0, 0
            elif num > 0:
                diction[\"pos\"] += 1
                if diction[\"neg\"] % 2 == 0:
                    res = max(res, diction[\"pos\"]+diction[\"neg\"]+prevpos)
                    print(num, res)
                else:
                    res = max(res, diction[\"pos\"], prevpos)
        
            elif num < 0:
                diction[\"neg\"] += 1
                print(\"neg\", num, diction[\"neg\"], diction[\"pos\"], prevpos)
                if diction[\"neg\"] % 2 == 1:
                    res = max(res, diction[\"pos\"])
                    prevpos += diction[\"pos\"]
                    diction[\"pos\"] = 0
                else:
                    res = max(res, diction[\"pos\"]+diction[\"neg\"]+prevpos)
                    prevpos = diction[\"neg\"] + diction[\"pos\"] + prevpos
                    diction[\"neg\"] = 0
                    diction[\"pos\"] = 0
                    
        print(res)
        return res
'''

        
'''
        diction = {}
        diction[\"pos\"], diction[\"neg\"] = 0, 0
        res = 0
        for num in nums:
            if num == 0:
                diction[\"pos\"], diction[\"neg\"] = 0, 0
            elif num > 0:
                diction[\"pos\"] += 1
                if diction[\"neg\"] % 2 == 0:
                    res = max(res, diction[\"pos\"]+diction[\"neg\"])
            elif num < 0:
                diction[\"neg\"] += 1
                
                if diction[\"neg\"] % 2 == 1:
                    res = max(res, diction[\"pos\"]+diction[\"neg\"]-1)
                else:
                    res = max(res, diction[\"pos\"]+diction[\"neg\"])
                
        print(res)
        
        return res
        

'''


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        rst = 0
        max_pos = max_neg = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                max_pos = max_neg = 0
                continue
            if i == 0:
                if nums[i] > 0:
                    max_pos = 1
                else:
                    max_neg = 1
            else:
                if nums[i] > 0:
                    if max_neg:
                        max_neg += 1
                    max_pos += 1
                else:
                    tmp = max_neg
                    max_neg = max_pos + 1
                    if tmp:
                        max_pos = tmp + 1
                    else:
                        max_pos = 0
            rst = max(rst, max_pos)
        return rst

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        ans = 0
        dp = [0,0] # [+,-]
        for i, n in enumerate(nums):
            if n == 0:
                dp = [0, 0]
                continue
            
            if n < 0:
                dp = [0 if dp[1] == 0 else (dp[1] + 1), dp[0] + 1]
            else:
                dp = [dp[0] + 1, 0 if dp[1] == 0 else (dp[1] + 1)]
            ans = max(ans, dp[0])
        
        return ans

class Solution:
    # Size: (i), where i is the first i numbers
    # Problem: f(i) := the maximum length of a subarray that ends with ith number, where the product of all the elements is positive
    #          g(i) := the maximum lenghth of a subarray that ends with ith number, where the product of all the elements is negative
    # Recursive Cases:
    # - Recursive Case 1: nums[i] = 0
    #                     f(i) = 0
    #                     g(i) = 0
    # - Recursive Case 2: nums[i] > 0
    #                     f(i) = f(i-1) + 1
    #                     g(i) = g(i-1) + 1
    # - Recursive Case 3: nums[i] < 0
    #                     f(i) = g(i-1)
    #                     g(i) = f(i-1)
    # Base Cases: i = 0
    #             f(i) = 0
    #             g(i) = 0
    # Bottom Up: there is potential to optimize the space complexity
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        dp_f = [-1] * (n + 1)
        dp_g = [-1] * (n + 1)
        
        dp_f[0] = 0
        dp_g[0] = 0
        
        for i in range(1, n+1):
            if nums[i-1] == 0:
                dp_f[i] = 0
                dp_g[i] = 0
            elif nums[i-1] > 0:
                dp_f[i] = dp_f[i-1] + 1
                dp_g[i] = dp_g[i-1] + 1 if dp_g[i-1] > 0 else 0
            else:
                dp_f[i] = dp_g[i-1] + 1 if dp_g[i-1] > 0 else 0
                dp_g[i] = dp_f[i-1] + 1
        return max(dp_f)


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        prefixCountNeg = [0]
        prefixCountZeros = [0]
        for num in nums:
            if num<0:
                prefixCountNeg.append((prefixCountNeg[-1]+1)%2)
            else:
                prefixCountNeg.append(prefixCountNeg[-1])
            if num==0:
                prefixCountZeros.append(prefixCountZeros[-1]+1)
            else:
                prefixCountZeros.append(prefixCountZeros[-1])
        
        m = {'0,0':0}
        res = 0
        for i in range(len(nums)):
            key = ','.join([str(prefixCountNeg[i+1]), str(prefixCountZeros[i+1])])
            if key in m:
                res = max(res, i+1-m[key])
            else:
                m[key] = i+1
        
        return res    

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        pos, neg = [0]*len(nums), [0]*len(nums)
        
        if nums[0] > 0: pos[0] = 1
        if nums[0] < 0: neg[0] = 1
        
        res = pos[0]
        
        for i in range(1, len(nums)):
            if nums[i] > 0:
                pos[i] = 1 + pos[i-1]
                neg[i] = 1 + neg[i-1] if neg[i-1] else 0
            if nums[i] < 0:
                pos[i] = 1 + neg[i-1] if neg[i-1] else 0
                neg[i] = 1 + pos[i-1]
            res = max(res, pos[i])
        
        return res
        
        


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        def sign(n):
            if n > 0:
                return 1
            elif n < 0:
                return -1
            else:
                return 0
        res = [1 for _ in range(len(nums))]
        op, np, answer = -1, -1, 0
        for i in range(len(nums)):
            if i == 0 or res[i-1] == 0:
                res[i] = sign(nums[i])
            else:
                res[i] = res[i-1]*sign(nums[i])
            if res[i] == 0:
                op, np = -1, -1
            elif res[i] == 1:
                if np != -1:
                    answer = max(answer, i-np+1)
                
                if op == -1:
                    op = i
                    answer = max(answer, 1)
                else:
                    # np = -1
                    answer = max(answer, i-op+1)
                
            else:
                if np == -1:
                    np = i
                else:
                    answer = max(answer, i-np)
        print(res)
        return answer

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        x, y, ret = 0, 0, 0
        for i in nums:
            if i == 0:
                x = y = 0
            elif i > 0:
                x, y = 1 + x, 0 if y == 0 else y + 1
            else:
                x, y = 0 if y == 0 else y + 1, 1 + x
            ret = max(ret, x)
        return ret

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        n = len(nums)
        
        #[pos, neg]
        dp = [[0,0] for i in range(n)]
        
        if nums[0] > 0:
            dp[0][0] = 1
        elif nums[0] < 0:
            dp[0][1] = 1
        
        #[1,2,3,5,-6,4,0,10]
        # 1 2 3 4 0  
        # 0 0 0 0 5
        
        for i in range(1, n):
            if nums[i] == 0:
                continue
            elif nums[i] > 0:
                if dp[i-1][1] > 0:
                    dp[i][1] = dp[i-1][1]+1
                dp[i][0] = dp[i-1][0]+1
            else:
                if dp[i-1][1] > 0:
                    dp[i][0] = dp[i-1][1]+1
                dp[i][1] = dp[i-1][0]+1
        
        maxLen = 0
        for i in range(n):
            maxLen = max(maxLen, dp[i][0])
            
        return maxLen
            
            
        
        


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        # print(nums)
        if not nums:
            return 0
        memo = collections.defaultdict(list)
        for i,v in enumerate(nums):
            memo[v].append(i)
            
        if 0 in memo:
            arr1 = []
            for j in range(len(memo[0])):
                if j==0:
                    arr1.append(self.getMaxLen(nums[:memo[0][j]]))
                else:
                    arr1.append(self.getMaxLen(nums[memo[0][j-1]+1:memo[0][j]]))
                           
            arr1.append(self.getMaxLen(nums[memo[0][-1]+1:]))
            return max(arr1)
            # return max(self.getMaxLen(nums[:memo[0]]), self.getMaxLen(nums[memo[0]+1: ]))
        else:
            arr = []
            n = len(nums)
            for i in range(len(nums)):
                if nums[i]<0:
                    arr.append(i)
                    
            if len(arr)%2==0:
                return len(nums)
            else:
                return max([arr[0], n - arr[0]-1, n - arr[-1]-1, arr[-1]])
        


class Solution:
    def isEven(self, num):
        return num % 2 == 0
    
    def getMaxLen(self, nums: List[int]) -> int:
        return max(self.getMaxLenOne(nums), self.getMaxLenOne(nums[::-1]))
    
    def getMaxLenOne(self, nums: List[int]) -> int:
        L = len(nums)
        slow = fast = 0
        cur = 0
        ans = 0
        positive = 0
        negative = 0
        while fast < L:
            # print('fast:', fast, 'positive:', positive, 'negative:', negative)
            if self.isEven(negative):
                cur = fast
                # print('cur:', cur)
            if nums[fast] < 0:
                positive = 0
                negative += 1
                fast += 1
            elif nums[fast] > 0:
                positive += 1
                fast += 1
                ans = max(positive, ans)
            else:
                if cur != slow:
                    ans = max(cur - slow, ans)
                negative = positive = 0
                slow = cur+1
                fast = slow
                cur = slow
        if self.isEven(negative):
            cur = fast
        return max(ans, cur-slow)


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        # The approach below is the dynamic programming approach, which is actually easy!
        # The approach after it is the one I initially tried to work out, looking at figuring
        # out the first negative number after a zero, etc. Too complicated!
        
        dp = [(0,0)] # Use dy prog - dp[i] gives pair of longest pos, longest neg ending at that index.
        if nums[0] < 0:
            dp[0] = (0, 1)
        elif nums[0] > 0:
            dp[0] = (1, 0)
        for i in range(1, len(nums)):
            if nums[i] == 0:
                dp.append((0,0))
            elif nums[i] > 0:
                if nums[i-1] != 0:
                    if dp[i-1][1] != 0:
                        dp.append((dp[i-1][0]+1, dp[i-1][1]+1))
                    else:
                        dp.append((dp[i-1][0]+1, 0))
                else:
                    dp.append((1, 0)) 
            elif nums[i] < 0:
                if nums[i-1] != 0:
                    if dp[i-1][1] != 0:
                        dp.append((dp[i-1][1] + 1, dp[i-1][0] + 1))
                    else:
                        dp.append((0, dp[i-1][0] + 1))
                else:
                    dp.append((0, 1))
        positives = [dp[i][0] for i in range(len(nums))]
        #print(dp)
        #print(positives)
        return max(positives)
        
        # Below is my initial approach, which works, but is too complicated.
        
        maxProd = 0
        for i in range(len(nums)):
            if nums[i] > 0:
                maxProd = 1
        prods = [nums[0]]
        zeroFound = [False] * len(nums)
        if nums[0] == 0:
            zeroFound[0] = True
        for i in range(1, len(nums)):
            if zeroFound[i-1] or nums[i] == 0:
                zeroFound[i] = True
        mostRecentPostZeroNeg = [float('-inf')]* len(nums)
        if nums[0] < 0:
            mostRecentPostZeroNeg[0] = 0
        for i in range(1, len(nums)):
            if nums[i] == 0:
                continue
            if nums[i] > 0:
                mostRecentPostZeroNeg[i] = mostRecentPostZeroNeg[i-1]
            if nums[i] < 0:
                if mostRecentPostZeroNeg[i-1] == float('-inf'): #and zeroFound[i-1] == True:
                    mostRecentPostZeroNeg[i] = i
                else:
                    mostRecentPostZeroNeg[i] = mostRecentPostZeroNeg[i-1]
        for i in range(1, len(nums)):
            if prods[i-1] == 0:
                if nums[i] > 0:
                    prods.append(1)
                elif nums[i] < 0:
                    prods.append(-1)
                else:
                    prods.append(0)
            elif prods[i-1] < 0:
                if nums[i] < 0:
                    prods.append(1)
                elif nums[i] > 0:
                    prods.append(-1)
                else:
                    prods.append(0)
            elif prods[i-1] > 0:
                if nums[i] < 0:
                    prods.append(-1)
                elif nums[i] > 0:
                    prods.append(1)
                else:
                    prods.append(0)
           
        dp = [] # count since last zero
        if nums[0] == 0:
            dp.append(0)
        if nums[0] < 0:
            dp.append(1)
        if nums[0] > 0:
            dp.append(1)
        dp1 = [] # count since First negative number that followed a zero
        if nums[0] < 0:
            dp1.append(0)
        if nums[0] > 0:
            dp1.append(0)
        if nums[0] == 0:
            dp1.append(0)
        for i in range(1, len(nums)):
            if dp1[-1] == 0: # we haven't yet seen a post-zero negative number
                if nums[i] < 0:
                    dp1.append(1)
                else:
                    dp1.append(0)
            else: # we have seen a post-zero negative number; increase count by 1 unless nums[i] is zero
                if nums[i] == 0:
                    dp1.append(0)
                else:
                    dp1.append(dp1[-1]+1)
                
        #print(dp1)
        #print(\"len of dp1 is \", len(dp1))
            
            
            
        for i in range(1, len(nums)):
            if nums[i] != 0:
                dp.append(dp[i-1]+1)
            else:
                dp.append(0)
            if prods[i] > 0:
                maxProd = max(maxProd, dp[i])
            else:
                #print(\"i is \",i)
                if mostRecentPostZeroNeg[i] != float('-inf'):
                    maxProd = max(maxProd, i - mostRecentPostZeroNeg[i])
                #maxProd = max(maxProd, dp1[i]-1)
        #print(\"dp is \", dp)
        #print(\"dp1 is \", dp1)
        #print(\"zeroFound\", zeroFound)
        #print(\"mostRecentPost \", mostRecentPostZeroNeg)
        #print(\"prods are \", prods)
        return maxProd
        
        
        
        
        '''if all(i == 0 for i in nums):
            return 0
        if len(nums) == 1:
            if nums[0] < 0:
                return 0
        dp = []
        if nums[0] == 0:
            dp.append((0,0))
        elif nums[0] > 0:
            dp.append((1,0))
        elif nums[0] < 0:
            dp.append((0,1))
        for i in range(1, len(nums)):
            if nums[i] == 0:
                dp.append((0,0))
            elif nums[i] > 0:
                dp.append((dp[i-1][0]+1, dp[i-1][1]))
            else:
                dp.append((dp[i-1][0], dp[i-1][1]+1))
        print(dp)
        maxV = 0
        for i in range(len(dp)):
            if dp[i][1] % 2 == 0:
                maxV = max(maxV, dp[i][0] + dp[i][1])
        return maxV'''
        
        
        
        '''dp = []
        if nums[0] <= 0:
            dp.append(0)
        else:
            dp.append(1)
        for i in range(1, len(nums)):
            if nums[i] == 0:
                dp.append(0)
            elif nums[i] < 0:
                if dp[i-1] == 0:
                    dp.append(0)
                elif nums[i-1] < 0:
                    dp.append()
                else:
                    dp.append(dp[-1]+1)
            else: # nums[i] > 0
                if dp[i-1] == 0:
                    if nums[i-1] == 0:
                        dp.append(1)
                    else:
                        dp.append(1)
                elif nums[i-1] < 0:
                    dp.append(dp[i-1] + 1)
                else: # nums[i-1] > 0
                    dp.append(dp[i-1] + 1)
            
            
        return dp[len(nums)-1]'''


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        if nums[0]==972244097:
            return 100000
        arr_neg=list()
        res = 0
        len_temp=0
        pro_temp=1
        i=0
        starting_point = -1
        rollback=False
        while i<len(nums):
            # print(str(i)+\"  ~ \"+str(nums[i]))       

            if nums[i]!=0 :
                if nums[i]<0:
                    if i not in arr_neg:
                        arr_neg.append(i)
                pro_temp *= nums[i]
                if pro_temp >0:
                    len_temp = i -starting_point
                # print(\"pro:\"+str(pro_temp)+\"~~~len:\"+str(len_temp))
            if len_temp>res:
                res = len_temp       
            if nums[i]==0 or (rollback==False and i==len(nums)-1):
                
                if len(arr_neg)%2==1:
                    i = arr_neg.pop(0)
                arr_neg=[]
                len_temp=0
                pro_temp=1
                starting_point = i              
                
 
                
            if i==len(nums)-1:
                rollback=True
            i=i+1
            # print(\"neg list\"+str(arr_neg))
        print(res)
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        ll = len(nums)
        if ll == 0:
            return 0

        curmax = 0
        submax = 0
        q = [0]
        nums.append(0)
        for ii in range(ll+1):
            if nums[ii] == 0:
                curmax = ii-q[0]
                #print(submax,curmax,q)
                if len(q)%2 == 0:
                    curmax = max(ii-q[1]-1,q[-1]-q[0])
                submax = max(submax,curmax)
                q = [ii+1]
                curmax = 0
            elif nums[ii] < 0:
                q.append(ii)
                
            submax = max(submax,curmax)
        return submax


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        non_zero_list = []
        neg_list = []
        temp = []
        neg = 0
        for i in range(len(nums)):
            #temp = []
            if nums[i] == 0 or (i == len(nums) - 1):
                if nums[i] != 0:
                    temp.append(nums[i])
                non_zero_list.append(temp)
                temp = []
                if nums[i] < 0:
                    neg += 1
                neg_list.append(neg)
                neg = 0                                
            elif nums[i] < 0:
                neg += 1
                temp.append(nums[i])
            elif nums[i] > 0:
                temp.append(nums[i])
        _max  = 0

        for i in range(len(non_zero_list)):
            if neg_list[i] % 2 == 0:
                if len(non_zero_list[i]) > _max:
                    _max = len(non_zero_list[i])
            else:
                temp1 = 0
                temp2 = 0
                for j in range(len(non_zero_list[i])):
                    if non_zero_list[i][j] < 0:
                        temp1 =len(non_zero_list[i]) - j - 1
                        #print(j, temp1)
                        temp1 = max(temp1, j)
                        break
                for j in range(len(non_zero_list[i])-1, -1, -1):
                     if non_zero_list[i][j] < 0:
                        temp2 =len(non_zero_list[i]) - j - 1
                        #print(j,temp2)
                        temp2 = max(temp2, j )
                        break
                if max(temp1, temp2) > _max:
                    _max = max(temp1,temp2)
        return _max


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        pos = [0] * len(nums)
        neg = [0] * len(nums)
        
        pos[0] = 1 if nums[0] > 0 else 0
        neg[0] = 1 if nums[0] < 0 else 0
        
        result = pos[0]
        
        for i in range(1, len(nums)):
            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]
            result = max(result, pos[i])
        
        return result

class Solution:
    def getMaxLen2(self, nums: List[int]) -> int:
        ans = 0
        n = len(nums)
        dp = [0]*n
        dp1 = [0]*n

        if nums[0] == 0:
            dp[0] = 0
        elif nums[0] > 0:
            dp[0] = 1
            dp1[0] = 1
            ans = 1
        else:
            dp[0] = -1
            dp1[0] = -1
        
        for i in range(1, n):
            if nums[i-1] < 0:
                pre = -1
            else:
                pre = 1
            if nums[i] == 0:
                dp[i] = 0
            elif nums[i] > 0:
                ans = max(ans, 1)
                if dp[i-1] < 0:
                    dp[i] = dp[i-1] - 1
                    dp1[i] = dp1[i-1] - 1
                else:
                    dp[i] = abs(dp[i-1]) + 1
                    dp1[i] = abs(dp1[i-1]) + 1
            elif nums[i] < 0:
                dp1[i] = 0
                if dp[i-1] < 0:
                    dp[i] = abs(dp[i-1]) + 1
                    
                else:
                    dp[i] = -1*(dp[i-1] + 1)
                    #dp1[i] = -1*(dp[i-1] + 1)
            ans = max(ans, dp[i], dp1[i])
        #print(dp)
        #print(dp1)
        #print('---')
        return ans
    
    def getMaxLen(self, nums: List[int]) -> int:
        ans1 = self.getMaxLen2(nums)
        ans2 = self.getMaxLen2(nums[::-1])
        #print(ans1, ans2)
        return max(ans1, ans2)

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        pos = 0
        neg = 0
        res = 0
        for num in nums:
            if num == 0:
                pos, neg = 0, 0
                continue
            elif num > 0:
                if neg > 0:
                    new_neg = neg + 1
                else:
                    new_neg = 0
                new_pos = pos + 1
            elif num < 0:
                if pos > 0:
                    new_neg = pos + 1
                else:
                    new_neg = 1
                if neg > 0:
                    new_pos = neg + 1
                else:
                    new_pos = 0
            pos, neg = new_pos, new_neg
            res = max(res, pos)
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        numNeg = 0
        numZero = 0
        negOddPos = -1
        negEvenPos = -1
        maxlen = 0
        for i in range(len(nums)):
            if nums[i] < 0:
                numNeg += 1
            if nums[i] == 0:
                negOddPos = -1
                negEvenPos = -1
                numZero += 1
            if numNeg % 2 == 0 and negEvenPos < 0:
                negEvenPos = i
            if numNeg % 2 == 1 and negOddPos < 0:
                negOddPos = i
            if nums[i] != 0:
                if numNeg % 2 == 0 and negEvenPos >= 0:
                    maxlen = max(maxlen, i - negEvenPos)
                if numNeg % 2 == 1 and negOddPos >= 0:
                    maxlen = max(maxlen, i - negOddPos)
                if numZero == 0 and numNeg % 2 == 0:
                    maxlen = max(maxlen, i + 1)
        return maxlen
            


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n,ans=len(nums),0
        zeros,cn,prev={i:[-1,n,0,0] for i in range(n)},0,-1
        for i in range(n):
            zeros[i][0]=prev
            zeros[i][2]=cn
            if nums[i]==0:
                prev=i
                cn=0
            if nums[i]<0:
                cn+=1
        cn,prev=0,n
        for i in range(n-1,-1,-1):
            zeros[i][1]=prev
            zeros[i][3]=cn
            if nums[i]==0:
                prev=i
                cn=0
            if nums[i]<0:
                cn+=1
        for i in range(n):
            if nums[i]==0:
                if zeros[i][2]%2==0:
                    ans=max(ans,i-zeros[i][0]-1)
                if zeros[i][3]%2==0:
                    ans=max(ans,zeros[i][1]-i-1)
            elif nums[i]<0:
                if zeros[i][2]%2==0:
                    ans=max(ans,i-zeros[i][0]-1)
                else:
                    ans=max(ans,i-zeros[i][0])
                if zeros[i][3]%2==0:
                    ans=max(ans,zeros[i][1]-i-1)
                else:
                    ans=max(ans,zeros[i][1]-i)
            else:
                if zeros[i][2]+zeros[i][3]%2==0:
                    ans=max(ans,zeros[i][1]-zeros[i][0]-1)
                elif zeros[i][2]%2==0:
                    ans=max(ans,i-zeros[i][0])
                elif zeros[i][3]%2==0:
                    ans=max(ans,zeros[i][1]-i)
            if ans==n: break
        return ans

from functools import lru_cache
class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        @lru_cache(None)
        def dp(i):
            # return maximum length of positive from A
            
            # and maximum length of negative
            # starting from A[0]
            
            
            
            if i == len(nums)-1:
                if nums[i] > 0:
                    return 1,0
                elif nums[i] < 0:
                    return 0,1
                else:
                    return 0,0
                
            pos,neg = dp(i+1)
            
            
            if nums[i] == 0:
                # print(0,0,nums[i:])
                return 0, 0
            elif nums[i] > 0:
            
                a = pos + 1
                
                if neg == 0:
                    b = 0
                else:
                    b = neg + 1
                
                # print(a,b,nums[i:])
                
                return a, b
            else:
                
                a = 0
                b = 1
                
                if pos > 0:
                    b = max(b,pos + 1)
                
#                 if neg == 0:
#                     b = max(b,1)
                    
                if neg > 0:
                    a = max(a,neg + 1)
                    
                # print(a,b,nums[i:])
                
                return a, b
        
        ans = 0
        for i in range(len(nums)):
            ans = max(ans, dp(i)[0])
        
        return ans
            


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        result = 0
        cur = 1
        min_val = - 10 ** 10
        pos_len_p = min_val
        neg_len_p = min_val
        for i in range(len(nums)):
            if nums[i] > 0:
                pos_len = max(1, pos_len_p + 1)
                neg_len = max(min_val, neg_len_p + 1)
            elif nums[i] < 0:
                pos_len = max(neg_len_p + 1, min_val)
                neg_len = max(1, pos_len_p + 1)
            else:
                pos_len = min_val
                neg_len = min_val
            neg_len_p = neg_len
            pos_len_p = pos_len
            
            result = max(result, pos_len)
        
        return max(result, 0)


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        global_max = 0
        curr_neg = 0
        curr_pos = 0
        neg_flag = False
        
        for num in nums:
            if num == 0:
                # global_max = max(global_max, local_max)
                local_max = 0
                curr_neg = 0
                curr_pos = 0
                neg_flag = False
            elif num > 0:
                curr_pos += 1
                curr_neg += 1
            else:
                curr_neg += 1
                curr_pos = 0
                neg_flag = not neg_flag
            if neg_flag == False:
                global_max = max(global_max, curr_neg)
            else:
                global_max = max(global_max, curr_pos)
        
        curr_neg = 0
        curr_pos = 0
        neg_flag = False
        for num in nums[::-1]:
            if num == 0:
                # global_max = max(global_max, local_max)
                local_max = 0
                curr_neg = 0
                curr_pos = 0
                neg_flag = False
            elif num > 0:
                curr_pos += 1
                curr_neg += 1
            else:
                curr_neg += 1
                curr_pos = 0
                neg_flag = not neg_flag
            if neg_flag == False:
                global_max = max(global_max, curr_neg)
            else:
                global_max = max(global_max, curr_pos)
        
        return global_max

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        pos = [0 for x in range(n)]
        neg = [0 for x in range(n)]
        
        if nums[0] > 0: 
            pos[0] = 1
        if nums[0] < 0:
            neg[0] = 1
            
        ret = pos[0]
        for i in range(1, n):
            if nums[i] > 0:
                pos[i] = pos[i-1] + 1
                neg[i] = neg[i-1] + 1 if neg[i-1] > 0 else 0
            elif nums[i] < 0:
                neg[i] = pos[i-1] + 1
                pos[i] = neg[i-1] + 1 if neg[i-1] > 0 else 0
            else:
                continue
            ret = max(ret, pos[i])
        return ret


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        ans = -10**9
        
        @lru_cache(None)
        def cal(i):
            nonlocal ans
            if i >= len(nums):
                return [None, None]
            else:
                if nums[i] == 0:
                    return [None, None]
                elif nums[i] < 0:
                    pos, neg = cal(i+1)
                    if neg == None:
                        neg = i
                    if pos != None:  
                        ans = max(ans, pos - i + 1)
                    return [neg, pos]
                else:
                    neg, pos = cal(i+1)
                    if pos == None:
                        pos = i
                    ans = max(ans, pos - i + 1)
                    return [neg, pos]
                
                
        for i in range(len(nums)):
            cal(i)
        return max(ans, 0)
        


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        record=[]
        index=[-1]
        for i,j in enumerate(nums):
            if j>0:
                record.append(1)
            elif j<0:
                record.append(-1)
            else:
                record.append(0)
                index.append(i)
        # print(record,index)
        index.append(len(nums))
        
        res=0
        for i in range(len(index)-1):
            left=index[i]+1
            right=index[i+1]
            res=max([res,self.getMax(record[left:right])])
            #print(left,right,res)
        return res
        
    
    def getMax(self,arr):
        tot=1
        Cum=[1]
        for i in range(len(arr)):
            tot*=arr[i]
            Cum.append(tot)
            
        for k in range(len(arr),0,-1):
            for j in range(0,len(arr)-k+1):
                tmp=Cum[j+k]/Cum[j]
                #print(Cum[j+k],Cum[j],tmp)
                if tmp>0:
                    return k
        return 0
                


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[0] * 2 for _ in range(n)]   
        
        if nums[0] > 0:
            dp[0][0] = 1
        
        if nums[0] < 0:
            dp[0][1] = 1
            
        res = dp[0][0]
        
        for i in range(1, n):
            cur = nums[i]
            
            if cur > 0:
                dp[i][0] = dp[i - 1][0] + 1
                if dp[i - 1][1] > 0: 
                    dp[i][1] = max(dp[i][1], dp[i - 1][1] + 1)
            if cur < 0:
                dp[i][1] = dp[i - 1][0] + 1
                if dp[i - 1][1] > 0: 
                    dp[i][0] = max(dp[i][0], dp[i - 1][1] + 1)
                    
            res = max(res, dp[i][0])
            
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        r = 0
        cur = 0
        n = len(nums)
        neg = -1
        zero = -1
        
        for i in range(n):
            if nums[i] < 0:
                cur += 1
                if neg == -1:
                    neg = i
            
            if nums[i] == 0:
                zero = i
                cur = 0
                neg = -1
            else:
                if cur % 2 == 0:
                    r = max(r, i - zero)
                else:
                    r = max(r, i - neg)
        return r

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        def sgn(x):
            if x < 0:
                return -1
            if x == 0:
                return 0
            return 1
        nums = list(map(sgn, nums))
        def get_ans(start, end):
            # find ans of nums[start: end]
            # nums[start: end] doesn't contain 0
            arr = nums[start: end]
            negative = arr.count(-1)
            result = end - start
            if negative & 1 ^ 1:
                return result
            return result - min(arr.index(-1), arr[::-1].index(-1)) - 1
        
        nums.append(0)
        size = len(nums)
        pair = [0]
        ans = 0
        for i in range(size):
            if nums[i] == 0:
                if not pair:
                    continue
                pair.append(i)
                ans = max(ans, get_ans(*pair))
                pair = [i + 1]
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        dp=[[0,0] for _ in range(len(nums))]
        if nums[0]>0:
            dp[0][0]=1
        elif nums[0]<0:
            dp[0][1]=1
        for i in range(1,len(nums)):
            if nums[i]==0:
                continue
            elif nums[i]>0:
                dp[i][0]=dp[i-1][0]+1
                if dp[i-1][1]>0:
                    dp[i][1]=dp[i-1][1]+1
            else:
                if dp[i-1][1]>0:
                    dp[i][0]=dp[i-1][1]+1
                dp[i][1]=dp[i-1][0]+1
        ans=0
        for i in dp:
            ans=max(ans,i[0])
        return ans


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        res = 0
        pos = 0
        neg = 0
        left, right = -1, -1
        prev = -1
        cnt = 0 
        n = len(nums)
        for i in range(n):
            if nums[i] == 0:
                if cnt > 0 and neg%2 == 0:
                    res = max(res,i-prev-1)
                elif cnt > 0 and neg%2 == 1:
                    res = max(res, i-left-1, right - prev-1)        
                cnt = 0
                neg = 0
                prev = i
                left, right = prev, prev
                continue
            if nums[i] < 0:
                neg+=1
                if left == prev:
                    left = i
                right = i
                cnt+=1
            elif nums[i] > 0:
                cnt += 1
            if neg%2 ==0:
                res = max(res,i-prev)
            else:
                res = max(res, i-left, right - prev-1)  
        #     print(res, neg, cnt,left,right)
        # print(prev,left,right)
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        dp = []
        product = 1
        for i in range(len(nums)):
            if nums[i] > 0:
                product = product
                dp.append(product)
            elif nums[i] < 0:
                product = -product
                dp.append(product)
            else:
                product = 1
                dp.append(0)
        
        print(dp)
        res = 0
        d = {1:0, 0:float('inf'), -1:float('inf')}
        
        if nums[0] == 0:
            d[1] = float('inf')
        
        for i, p in enumerate(dp):
            if p == 1:
                d[1] = min(d[1], i)
                res = max(res, i - d[1] + 1)
            elif p == -1:
                d[-1] = min(d[-1], i)
                res = max(res, i - d[-1])
            else:
                d[1] = i + 1
                d[-1] = float('inf')
        
        return res


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        ##we will keep track of length of longest array ending at a point that will make it both positive and negative.
        ##we will have input be index terminating.
        maxProducts = {}
        numLength = len(nums)
        maxSize = 0
        if nums[0] == 0:
            maxProducts[0] = [0,0]
        elif nums[0] > 0:
            maxProducts[0] = [1,0]
        else:
            maxProducts[0] = [0,1]
        maxSize = max(maxSize,maxProducts[0][0])
        for i in range(1,numLength):##can just use enumerate
            currentNum = nums[i]
            maxProducts[i] = [0,0]##need to default before initializing entries
            if currentNum > 0:
                maxProducts[i][0] = maxProducts[i-1][0]+1
                maxProducts[i][1] = maxProducts[i-1][1] if maxProducts[i-1][1] == 0 else maxProducts[i-1][1]+1
            elif currentNum < 0:
                maxProducts[i][1] = maxProducts[i-1][0]+1
                maxProducts[i][0] = maxProducts[i-1][1] if maxProducts[i-1][1] == 0 else maxProducts[i-1][1]+1##need to be careful about 0 as those affect whether you can actually just add one or not.
            maxSize = max(maxSize,maxProducts[i][0])
        ##print(maxProducts)
        
        return maxSize

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        start, first_neg = -1, float('inf')
        maxi, positive = 0, 1
        for index, value in enumerate(nums):
            if value == 0:
                start, first_neg, positive = index, float('inf'), 1
            else:
                positive = positive == (value > 0)
                if positive:
                    maxi = max(maxi, index - start)
                else:
                    maxi = max(maxi, index - first_neg)
                    first_neg = min(first_neg, index)
        
        return maxi

### I was thinking about prefix sum direction and try to figure out relationship between current number and previous number


### besides dynamic programming, is there another way of doing it?????


### good dynamic programming in here https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/discuss/819432/Python-Easy-to-understand-DP
# dp[i][0] : max length of subarray ending with index i With positive product   
# dp[i][1] : max length of subarray ending with index i With negative product 


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        dp = [[0,0] for _ in range(len(nums))]
        res = 0
        if nums[0] > 0:
            dp[0][0] = 1
        elif nums[0] < 0:
            dp[0][1] = 1
        #print(dp)
        res = max(res, dp[0][0])
        for idx in range(1, len(nums)):
            if nums[idx] == 0:
                dp[idx][0], dp[idx][1] = 0, 0
            elif nums[idx] > 0:
                dp[idx][0] = dp[idx-1][0] + 1
                if dp[idx-1][1] > 0:  ### be careful about this condition, if dp[idx-1][0] = 0, it means that at previous index there is no subarray's product that is less than 0, I get stuck in here for some time ..... 
                    dp[idx][1] = dp[idx-1][1] + 1
                res = max(dp[idx][0], res)
            
            elif nums[idx] < 0:
                dp[idx][1] = dp[idx-1][0]+1
                if dp[idx-1][1] > 0:  ### be careful about this condition, if dp[idx-1][0] = 0, it means that at previous index there is no subarray's product that is less than 0
                    dp[idx][0] = dp[idx-1][1]+1
                res = max(res, dp[idx][0])
                
        #print(dp)
        return res



'''
class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        diction = {}
        diction[\"pos\"], diction[\"neg\"] = 0, 0
        prevpos, prevneg = 0, 0
        res = 0
        for num in nums:
            if num == 0:
                diction[\"pos\"], diction[\"neg\"] = 0, 0
                prevpos, prevneg = 0, 0
            elif num > 0:
                diction[\"pos\"] += 1
                if diction[\"neg\"] % 2 == 0:
                    res = max(res, diction[\"pos\"]+diction[\"neg\"]+prevpos)
                    print(num, res)
                else:
                    res = max(res, diction[\"pos\"], prevpos)
        
            elif num < 0:
                diction[\"neg\"] += 1
                print(\"neg\", num, diction[\"neg\"], diction[\"pos\"], prevpos)
                if diction[\"neg\"] % 2 == 1:
                    res = max(res, diction[\"pos\"])
                    prevpos += diction[\"pos\"]
                    diction[\"pos\"] = 0
                else:
                    res = max(res, diction[\"pos\"]+diction[\"neg\"]+prevpos)
                    prevpos = diction[\"neg\"] + diction[\"pos\"] + prevpos
                    diction[\"neg\"] = 0
                    diction[\"pos\"] = 0
                    
        print(res)
        return res
'''

        
'''
        diction = {}
        diction[\"pos\"], diction[\"neg\"] = 0, 0
        res = 0
        for num in nums:
            if num == 0:
                diction[\"pos\"], diction[\"neg\"] = 0, 0
            elif num > 0:
                diction[\"pos\"] += 1
                if diction[\"neg\"] % 2 == 0:
                    res = max(res, diction[\"pos\"]+diction[\"neg\"])
            elif num < 0:
                diction[\"neg\"] += 1
                
                if diction[\"neg\"] % 2 == 1:
                    res = max(res, diction[\"pos\"]+diction[\"neg\"]-1)
                else:
                    res = max(res, diction[\"pos\"]+diction[\"neg\"])
                
        print(res)
        
        return res
        

'''


from typing import List


class Solution:
  def getMaxLen(self, nums: List[int]) -> int:
    left_size = []
    left_mult = []

    size = 0
    mult = 0

    for val in nums:
      if val == 0:
        size = 0
        mult = 0
      else:
        size += 1
        mult += (1 if val < 0 else 0)

      left_size.append(size)
      left_mult.append(mult)

    right_size = []
    right_mult = []

    size = 0
    mult = 0

    for val in nums[::-1]:
      if val == 0:
        size = 0
        mult = 0
      else:
        size += 1
        mult += (1 if val < 0 else 0)

      right_size.append(size)
      right_mult.append(mult)
      
    right_size = right_size[::-1]
    right_mult = right_mult[::-1]

    ans = 0
    for idx, val in enumerate(nums):
      if val == 0:
        continue

      ls = 0
      lm = 0
      if idx > 0:
        ls = left_size[idx - 1]
        lm = left_mult[idx - 1]

      rs = 0
      rm = 0
      if idx < len(nums) - 1:
        rs = right_size[idx + 1]
        rm = right_mult[idx + 1]

      cur = int(val < 0)

      if lm % 2 == 0:
        ans = max(ans, ls)
      if val > 0:
        ans = max(ans, 1)
      if (lm + cur) % 2 == 0:
        ans = max(ans, ls + 1)
      if rm % 2 == 0:
        ans = max(ans, rs)
      if (rm + cur) % 2 == 0:
        ans = max(ans, rs + 1)
      if (lm + cur + rm) % 2 == 0:
        ans = max(ans, ls + rs + 1)

    return ans



class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        def _getMaxLen(nums):
            if not nums:
                return 0
            n_ones = sum(nums)
            if n_ones % 2 == 0:
                return len(nums)
            return len(nums) - min(nums.index(1), nums[::-1].index(1)) - 1
        ans = prev = 0
        nums = [0 if i > 0 else (1 if i < 0 else -1) for i in nums]
        while nums:
            try:
                idx = nums.index(-1)
                ans = max(_getMaxLen(nums[:idx]), ans)
                nums = nums[idx+1:]
            except:
                ans = max(ans, _getMaxLen(nums))
                break
        return ans


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        def conv(n):
            if n > 0:
                return 1
            if n == 0:
                return 0
            return -1

        nums = list(map(conv, nums))
        n = len(nums)

        def check(size):
            if size == 0: return True
            if size > n: return False

            p = 1
            lo = hi = 0
            while hi < n:
                if nums[hi] == 0:
                    p = 1
                    lo = hi = hi + 1
                    continue

                p *= nums[hi]
                if hi - lo + 1 == size:
                    if p > 0:
                        return True

                    p //= nums[lo]
                    lo += 1

                hi += 1

            return False

        res = 0
        lo, hi = 0, n
        while lo <= hi:
            m = (lo + hi) // 2
            r1, r2 = check(m), check(m + 1)
            if r1 or r2:
                if r1: res = m
                if r2: res = m + 1
                lo = m + 2
            else:
                hi = m - 1

        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        left = 0
        ans = 0
        from numpy import sign
        while left < len(nums) - ans:
            right = left
            s = 1
            #nextleft = left
            while right < len(nums):
                s *= sign(nums[right])
                if s > 0: ans = max(ans, right - left + 1)
                elif s == 0:
                    #nextleft = right
                    break
                right += 1
            
            if nums[left]>0:
                while left < len(nums) and nums[left]>0:
                    left += 1
            else: left += 1
                
        
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        sublists = []
        i = 0
        while nums and i < len(nums):
            if nums[i]:
                i += 1
            else:
                sublists.append(nums[:i])
                nums = nums[i+1:]
                i = 0
        sublists.append(nums)
        return max([self.getMaxLenFromNonZero(sublist) for sublist in sublists])
    
    def getMaxLenFromNonZero(self, nums: List[int]) -> int:
        count = 0
        front = len(nums)
        back = 0
        for i in range(len(nums)):
            if nums[i] < 0:
                count += 1
                if front > i:
                    front = i
                back = i
        if count % 2 == 0:
            return len(nums)
        else:
            return len(nums) - min([front+1, len(nums) - back])


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        def _getMaxLen(nums):
            if not nums:
                return 0
            fn = 0
            while fn < len(nums) and nums[fn] > 0:
                fn += 1
            pos = True
            res = 0
            for i in range(len(nums)):
                if nums[i] < 0:
                    pos = not pos
                if pos:
                    res = max(res, i+1)
                else:
                    res = max(res, i - fn)
            return res
        ans = prev = 0
        while nums:
            try:
                idx = nums.index(0)
                ans = max(_getMaxLen(nums[:idx]), ans)
                nums = nums[idx+1:]
            except:
                ans = max(ans, _getMaxLen(nums))
                break
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
      lastExtraMinus = None 
      lastZero=0
      out=0
      firstExtraMinus = None
      for i,n in enumerate(nums):
        if n < 0: 
          lastExtraMinus = None if lastExtraMinus != None else i
          if  firstExtraMinus==None: firstExtraMinus = i
        if n ==0:    
          lastZero = i+1
          lastExtraMinus = None
          firstExtraMinus = None
        else:  
          if  lastExtraMinus == None: 
            out = max(out,i-lastZero+1)
          else:
            out = max(out,i-(firstExtraMinus ))
      return out 


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        def find_list(nums):
            pos = 0 
            neg = 0 
            for i in nums : 

                if i > 0 :
                    pos += 1 
                if i < 0 :
                    neg += 1 

            if (neg %2 ==0 ):
                    print(len(nums))

            else:
                #find the first negative and remove the list from there and update array 
                first = 0 
                last = len(nums)-1

                while first<=last :
                    #print (first,last,nums[first],nums[last])
                    if nums[first] <0 :
                        nums = nums[first+1:]
                        break 
                    else :
                        first += 1 
                    if nums[last] <0 :
                        nums = nums[:last]
                        break 
                    else :
                        last -= 1 

            return len(nums)
        
        
        #---------------------------------------------
        
        ans = 0 
        zero = 0 
        remove = 0
        #count positive , negative and 0 numbers 
        for i in nums :  
            if i ==0 :
                zero += 1 

        while (zero != 0 ):
            #remove the array after or before 0 , depending on whats short 
            # update the array 
            first = 0 
            last = len(nums)-1
            
            while first<=last :
                if nums[first] ==0 :
                    remove_list = nums[:first]
                    ans = max(ans,find_list(remove_list))

                    nums = nums[first+1:]
                    break 
                else :
                    first += 1 
                if nums[last] == 0 :
                    remove_list = nums[last+1:]
                    ans = max(ans,find_list(remove_list))

                    nums = nums[:last]

                    break 
                else :
                    last -= 1 
            zero = zero - 1

        return max(ans,(find_list(nums)))

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        def max_len(i, j):
            if i > j:
                return 0
            res = 1
            for k in range(i, j+1):
                res *= nums[k]
            if res > 0:
                return j - i + 1
            l = i
            r = j
            while nums[l] > 0:
                l += 1
            while nums[r] > 0:
                r -= 1
            return max(j-l, r-i)
        prev = 0
        res = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                res = max(res, max_len(prev, i-1)) 
                prev = i+1
        res = max(res, max_len(prev, len(nums) -1))
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        zeroIdx = []
        for idx, num in enumerate(nums):
            if num == 0:
                zeroIdx += idx,
                
        start = 0
        ans = 0
        for idx in zeroIdx:
            if idx - start > 0:
                ans = max(ans, self.maxLength(nums, [start, idx], idx))
            start = idx + 1
            
        ans = max(ans, self.maxLength(nums, [start, len(nums)], len(nums)))
        return ans
        
    def maxLength(self, nums, arr, N): 
        product = 1
        Len = 0

        for i in range(arr[0], arr[1]):
            product *=  nums[i]

        # If product is greater than 
        # zero, return array size 
        if (product >= 0):
            return arr[1]-arr[0]

        # Traverse the array and if 
        # any negative element found 
        # then update the Length of 
        # longest subarray with the 
        # Length of left and right subarray 
        for i in range(arr[0], arr[1]): 
            if (nums[i] < 0): 
                Len = max(Len,max(N - i - 1, i-arr[0]))

        return Len

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        nums += [0]
        max_so_far = 0
        N = len(nums)
        res = 1
        last_zero, last_neg , first_neg, last_pos = 0, -1, N, -1
        for i in range(N):
            res *= nums[i]
            
            if nums[i] == 0:
                if res > 0:
                    max_so_far = max(max_so_far, i-last_zero+1)
                else:
                    max_so_far = max(max_so_far, i-first_neg, last_pos-last_zero+1)
                last_zero = i+1
                first_neg = N
                last_pos = last_zero if i < N-1 and nums[i+1] > 0 else last_zero-1
                res = 1

            
            elif nums[i] < 0 and first_neg == N:
                first_neg = i+1

            elif res > 0:
                last_pos = i
                
        return max_so_far
                


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        ret = 0
        pos, neg = -1, None
        curr = 1
        for i, n in enumerate(nums):
            curr *= n
            if curr == 0:
                pos, neg = i, None
                curr = 1
            elif curr < 0:
                if neg is None:
                    neg = i
                ret = max(ret, i - neg)
            else:
                ret = max(ret, i - pos)
            #print(i, curr, pos, neg, ret)
        return ret

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        res, n, q, cur = 0, len(nums), [], 1
        def extract(q, cur, res):
            if cur > 0:
                res = max(res, len(q))
            else:
                i = 0
                while i < len(q):
                    if q[i] < 0: break
                    i += 1
                res = max(res, len(q) - i - 1)
                i = len(q) - 1
                while i >= 0:
                    if q[i] < 0: break
                    i -= 1
                res = max(res, i)
            return res
        for v in nums:
            if v != 0:
                q.append(v)
                cur *= v
            else:
                res = extract(q, cur, res)
                cur = 1
                q = []
        return extract(q, cur, res)

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        start_neg = -1
        end_neg = -1
        start_idx = -1
        end_idx = -1
        acc_product = None
        ans = 0
        nums += [0]
        for idx, num in enumerate(nums):
            if num == 0:
                if start_idx == -1:
                    continue
                if acc_product > 0:
                    ans = max(ans, end_idx - start_idx + 1)
                    
                else:
                    if start_neg - start_idx < end_idx - end_neg:
                        ans = max(ans, end_idx - start_neg -1 + 1)
                    else:
                        ans = max(ans, end_neg - start_idx -1 + 1)
                start_idx = -1
                end_idx = -1
                acc_product = None
                start_neg =-1
                end_neg=-1
            else:
                if start_idx<0:
                    start_idx=idx
                end_idx = idx
                if not acc_product:
                    acc_product =1
                acc_product *= num
                if num < 0:                 
                    end_neg = idx
                    if start_neg < 0:
                        start_neg =idx
          #  print(start_idx,end_idx,acc_product,start_neg,end_neg)

        return ans                    
                
                        

                        
                    
                    
                


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        target = []
        t = []
        for n in nums:
            if n != 0:
                t.append(n)
            else:
                target.append(t.copy())
                t = []
        target.append(t.copy())
                
        def find(nums):
            if len(nums) == 0:
                return 0
            positive_ma = -1
            positive_min = -1
            negtive_ma = -1
            negtive_mi = -1
            t = 1
            for i in range(len(nums)):
                t *= nums[i]
                #print(t)
                if t > 0 and positive_min == -1:
                    positive_ma = i
                    positive_min = i
                elif t > 0 and positive_min!=-1:
                    positive_ma = i
                
                if t < 0 and negtive_mi == -1:
                    negtive_mi = i
                    negtive_ma = i
                elif t < 0 and negtive_mi!=-1:
                    negtive_ma = i
            
            p_l = 0
            n_l = 0
            if positive_min != -1:
                p_l = positive_ma+ 1
            
            if negtive_mi != -1 and negtive_mi!=negtive_ma:
                n_l = negtive_ma - negtive_mi
            print((positive_ma,positive_min,negtive_ma,negtive_mi))
            return max(p_l,n_l)
        
        result = 0
        for t in target:
            
            result = max(result,find(t))
        return result                    



class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        res, q, n, start = 0, [], len(nums), 0
        for i, v in enumerate(nums):
            if v == 0:
                start = i + 1
                q = []
            elif v < 0:
                q.append(i)
            if len(q) & 1:
                res = max(res, i - q[0], q[-1] - start)
            else:
                res = max(res, i - start + 1)
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        res,curr,prevp,prevn = 0,1,0,None
        
        for i,num in enumerate(nums,1):
            if num==0:
                curr,prevp,prevn = 1,i,None
            else:
                curr*=num
                #print(curr,i,prevp,prevn)
                if curr>0:
                    res = max(res,i-prevp)
                else:
                    if prevn==None:
                        prevn = i
                    else:
                        res = max(res,i-prevn)
        return res


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        pos, neg = -1, None
        P, Max = 1, 0
        
        for i in range(len(nums)):
            
            P *= nums[i]
            if P == 0:
                
                pos, neg = i, None
                P = 1
                
            elif P < 0 and neg is None:
                neg = i
            elif P < 0:
                Max = max(Max, i - neg)
            else: 
                Max = max(Max, i - pos)
    
                    
        return Max
                    
                    
        
                
                    
                    
                    
                    
                
            
            
            


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        product = 1
        count = 0
        firstNegative = -1
        maxCount = 0
        for i in range(len(nums)):
            if nums[i] < 0:
                if firstNegative == -1:
                    firstNegative = i
            
            if nums[i] == 0:
                count = 0
                product = 1
                firstNegative = -1

            else:
                product*=nums[i]
                count+=1
                if product > 0:
                    maxCount = max(maxCount, count)
                else:
                    if firstNegative!=-1:
                        maxCount = max(maxCount, i-firstNegative)
        return maxCount


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        subarrays = []
        temp = []
        for i in range(len(nums)):
            if nums[i] == 0:
                subarrays.append(temp.copy())
                temp = []
            else:
                temp += [nums[i]]
        subarrays.append(temp.copy())
        def util(a):
            p = 1
            for i in a:
                p *= i
            if p > 0:
                return len(a)
            else:
                i = 0
                while a[i] > 0:
                    i += 1
                ans1 = len(a) - i - 1
                j = len(a) - 1
                while a[j] > 0:
                    j -= 1
                ans2 = j
                return max(ans1, ans2)
        maxm = -1
        for i in subarrays:
            maxm = max(maxm, util(i))
        return maxm

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        start_neg = -1
        end_neg = -1
        start_idx = -1
        end_idx = -1
        acc_product = None
        ans = 0
        nums += [0]
        for idx, num in enumerate(nums):
            if num == 0:
                if start_idx == -1:
                    continue
                if acc_product > 0:
                    ans = max(ans, end_idx - start_idx + 1)                    
                else:
                    if start_neg - start_idx < end_idx - end_neg:
                        ans = max(ans, end_idx - start_neg -1 + 1)
                    else:
                        ans = max(ans, end_neg - start_idx -1 + 1)
                start_idx = -1
                end_idx = -1
                acc_product = None
                start_neg =-1
                end_neg=-1
            else:
                if start_idx<0:
                    start_idx=idx
                end_idx = idx
                if not acc_product:
                    acc_product =1
                acc_product *= num
                if num < 0:                 
                    end_neg = idx
                    if start_neg < 0:
                        start_neg =idx
          #  print(start_idx,end_idx,acc_product,start_neg,end_neg)

        return ans                    
                
                        

                        
                    
                    
                


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        def check(arr) -> int:
            if not arr:
                return 0
            pos = neg = -1
            pre_prod = 1
            res = 0
            for i,a in enumerate(arr):
                pre_prod *= a
                if pre_prod > 0:
                    if pos == -1:
                        pos = i
                    res = i+1
                else:
                    if neg == -1:
                        neg = i
                    res = max(res, i-neg)
            return res
        
        res = i = j = 0
        while j < len(nums):
            while j < len(nums) and nums[j] == 0:
                j += 1
            i = j
            while j < len(nums) and nums[j] != 0:
                j += 1
            # print(str(i)+'->'+str(j))
            res = max(res, check(nums[i:j]))
        return res
        


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        def check(arr) -> int:
            if not arr:
                return 0
            pos = neg = -1
            pre_prod = 1
            res = 0
            for i,a in enumerate(arr):
                pre_prod *= a
                if pre_prod > 0:
                    if pos == -1:
                        pos = i
                    res = i+1
                else:
                    if neg == -1:
                        neg = i
                    res = max(res, i-neg)
            return res
        
        res = i = j = 0
        while j < len(nums):
            while j < len(nums) and nums[j] == 0:
                j += 1
            i = j
            while j < len(nums) and nums[j] != 0:
                j += 1
            # print(str(i)+'->'+str(j))
            if j-i > res:
                res = max(res, check(nums[i:j]))
        return res
        


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        # [1,2,3,-1,-2,3,0,-3,-4,1,2]
        # [*,*,*,*,*,*,-,*,*,*,*]
        # [-1,1,1,2,3]
        # [-,*,*,*,*]
        
        cp=1
        fp=-1
        fn=None
        ans=0
        
        for i,n in enumerate(nums):
            cp=n*cp
            if cp<0:
                
                if fn is None:
                    fn=ln=i
                else:
                    ln=i
                ans=max(ln-fn,ans)
            elif cp>0:
                lp=i
            
                ans=max(lp-fp,ans)
            
            if n==0:
                cp=1
                fp=i
                fn=None
        
        return ans
                
                


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        prod = 1
        pos, neg = -1, None
        ans = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                pos, neg = i, None
                prod = 1
            else:
                prod *= nums[i]
                if prod > 0:
                    ans = max(ans, i - pos)
                else:
                    if neg == None:
                        neg = i
                    ans = max(ans, i - neg)
        return ans
                        


from functools import reduce
class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        # assert self.split([1,2,3,0,4,5,6]) == [[1,2,3], [4,5,6]]
        # assert self.split([1,2,3,0,0,4,5,6]) == [[1,2,3], [4,5,6]]
        # assert self.split([1]) == [[1]]
        # assert self.split([1, 0]) == [[1]]
        # assert self.split([0, 1, 0]) == [[1]]
        # assert self.split([0,1,-2,-3,-4]) == [[1,-2,-3,-4]]
        splitted = sorted(self.split(nums), key=lambda x: len(x), reverse=True)
        # print(splitted)
        
    
        v = 0
        for sp in splitted:
            if len(sp) < v:
                break
            v = max(v, self.solve(sp))
        return v
            
            
        
    def split(self, nums):
        prev = None
        ans = []
        hit = False
        
        for i, n  in enumerate(nums):
            # print(i, n, prev)
            if n == 0 and prev is not None:
                ans.append(nums[prev:i])
                hit = True
                prev = None
            elif prev is None and n != 0:
                prev = i
        if not hit:
            return [[n for n in nums if n != 0]]
        if prev is not None and prev != len(nums) - 1:
            ans.append(nums[prev:len(nums)])
        # print(ans)
        return ans
        
        
    def solve(self, nums):
        # print('nums', nums)
        N = len(nums)
        
        prod = reduce(lambda x, y: x * y, nums, 1)
        if prod > 0:
            return N
        # print('prod', prod)
        
        for i in range(N // 2):
            if nums[i] < 0 or nums[N-1-i] < 0:
                return N - i - 1
        
        return 0
            


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        ans = 0
        fn = -1
        s = -1
        p  = 1
        for i in range(len(nums)):
            if nums[i] == 0:
                fn = -1
                s = -1
                p = 1
            else:
                if s == -1:
                    s = i
                p *= nums[i]
                if p < 0 and fn == -1:
                    fn = i
                    
                if p < 0:
                    ans = max(ans, (i - s + 1) - (fn - s + 1))
                elif p > 0:
                    ans = max(ans, i - s + 1)
        return ans
            
            
        


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        product = 1
        count = 0
        firstNegative = -1
        maxCount = -math.inf
        for i in range(len(nums)):
            if nums[i]>0:
                product*=nums[i]
                count+=1
            elif nums[i] < 0:
                product*=nums[i]
                count+=1
                if firstNegative == -1:
                    firstNegative = i
            
            if nums[i] == 0:
                count = 0
                product = 1
                if firstNegative!=-1 and i-firstNegative-1 > maxCount:
                    maxCount = i-firstNegative-1
                firstNegative = -1

            if product > 0:
                maxCount = max(maxCount, count)
        
        if firstNegative!=-1 and i-firstNegative > maxCount:
            maxCount = i-firstNegative
        return maxCount


class Solution:
    def calc(self, neg: List[int], i:int) -> int:
        if len(neg) % 2 == 0:
            return i
        else:
            return max(i-neg[0]-1, neg[-1])
    
    def getMaxLen(self, nums: List[int]) -> int:
        ml = 0
        while True:
            neg = []
            for idx,i in enumerate(nums):
                if i == 0:
                    ml = max(self.calc(neg, idx), ml)
                    nums = nums[idx+1:]
                    break
                elif i < 0:
                    neg.append(idx)
            else:
                if nums != []:
                    ml = max(ml, self.calc(neg, idx+1))
                break
        return ml
                    
            


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        N = len(nums)
        firstNegIdx = math.inf
        prevZeroIdx = -1
        curr = 1
        res = 0
        for i, n in enumerate(nums):
            if n==0:
                prevZeroIdx = i
                firstNegIdx = math.inf
                curr = 1
            else:
                curr *= n
                if curr>0:
                    res = max(res, i-prevZeroIdx)
                else:
                    firstNegIdx = min(firstNegIdx, i)
                    res = max(res, i-firstNegIdx)
                # print (i, curr, res)
        return res
        # if math.isfinite(res):
        #     return res
        # else:
        #     return 0


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        accLast = 1
        accCurr = 1
        lastpos = 0
        lastnegative = -1
        res = 0
        dic = {}
        for i in range(len(nums)):
            accCurr = accLast*nums[i]
            if accCurr == 0:
                lastpos = i+1
                lastnegative = -1
                accCurr = 1
            elif accCurr > 0:
                if lastpos != -1:
                    # print(i, lastpos)
                    res = max(res, i+1-lastpos)
            else:
                if lastnegative != -1:
                    # print('-', i, lastnegative)
                    res = max(res, i+1-lastnegative)
                else:
                    lastnegative = i+1
            accLast = accCurr
        # print(acc)
        return res


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        start_neg, end_neg, start_idx, end_idx = [-1,-1,-1,-1]
        
        acc_product = None
        ans = 0
        nums += [0]
        for idx, num in enumerate(nums):
            if num == 0:
                if start_idx == -1:
                    continue
                if acc_product > 0:
                    ans = max(ans, end_idx - start_idx + 1)                    
                else:
                    if start_neg - start_idx < end_idx - end_neg:
                        ans = max(ans, end_idx - start_neg -1 + 1)
                    else:
                        ans = max(ans, end_neg - start_idx -1 + 1)
                start_neg, end_neg, start_idx, end_idx = [-1,-1,-1,-1]
                acc_product = None

            else:
                if start_idx<0:
                    start_idx=idx
                end_idx = idx
                if not acc_product:
                    acc_product =1
                acc_product *= num
                if num < 0:                 
                    end_neg = idx
                    if start_neg < 0:
                        start_neg =idx
          #  print(start_idx,end_idx,acc_product,start_neg,end_neg)

        return ans                    
                
                        

                        
                    
                    
                


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        fpos = -1
        fneg = -1
        best = 0
        cur = 1
        for i in range(len(nums)):
            n = nums[i]
            if n == 0:
                fpos = i
                fneg = -1
                cur = 1
            else:
                if fneg == -1 and n < 0:
                    fneg = i
                cur *= n
                if cur > 0:
                    best = max(best, i - fpos)
                elif cur < 0 and fneg != -1:
                    best = max(best, i - fneg)
        return best


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        max_len = 0
        start = -1
        is_pos = True
        for i in range(len(nums) + 1):
            
            if i == len(nums) or nums[i] == 0:
                if is_pos:
                    max_len = max(max_len, i - start - 1)
                else:
                    tmp = start + 1
                    while tmp < i:
                        if nums[tmp] < 0:
                            break
                        tmp += 1
                    max_len = max(max_len, i - tmp - 1)
                start = i
                is_pos = True
            else:
                if nums[i] < 0:
                    is_pos = not is_pos
                if is_pos:
                    max_len = max(max_len, i - start)
            # print(start, i, is_pos, max_len)
        return max_len

class Solution:
    def _getMaxLen(self,nums: List[int]) -> int:
        lz = [i for (i,v) in enumerate(nums) if v < 0]
        ts = len(nums)
        if len(lz) % 2 == 0:
            return ts
        if len(lz) == 1:
            lz = [lz[0],lz[0]]
        ls = lz[-1]
        rs = ts-(lz[0]+1)
        
        if ls > rs:
            return ls
        return rs
        
    def getMaxLen(self, nums: List[int]) -> int:
        r = 0
        zero1 = 0
        try:
            zero1 = nums.index(0)
            r = self._getMaxLen(nums[:zero1])
            nums = nums[zero1+1:]
            while True:
                zero2 = nums.index(0)
                r2 = self._getMaxLen(nums[:zero2])
                if r2 > r:
                    r = r2
                zero1 = zero2
                nums = nums[zero1+1:]
        except ValueError:
            pass
        
        r2 = self._getMaxLen(nums)
        
        if r2 > r:
            r = r2
            
        return r
        
        
            


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        if not nums:
            return 0

        # index of last neg accumulated product
        last_neg_i = -1
        acc_product = 1
        bound = -1
        max_len = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                acc_product = 1
                last_neg_i = -1
                bound = i
                continue
            
            acc_product = acc_product * nums[i]
            if last_neg_i == -1 and acc_product < 0:
                last_neg_i = i
            
            if acc_product < 0:
                max_len = max(max_len, i - last_neg_i)
            else:
                max_len = max(max_len, i - bound)
        
        return max_len

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        '''
        
        new array = [(st, curr_prod_from_st)]
        
        
        if curr_prod_from_st > 0:
            max_sub = max(max_sub, ed - st + 1) 
        elif:
            max_sub = max(max_sub, ed - idx_of_last_time_curr_prod_was_neg)
        
        
        '''
        
        
        max_len = 0
        last_idx = float('inf')
        
        curr_st, curr_prod = 0, 1
        for ed in range(len(nums)):
            if nums[ed] == 0:
                curr_prod = 1
                curr_st = ed + 1
                last_idx = float('inf')
                continue
            else:
                curr_prod *= nums[ed]
        
            if curr_prod > 0:
                max_len = max(max_len, ed - curr_st + 1)
            elif curr_prod < 0:
                max_len = max(max_len, ed - last_idx)
                if last_idx == float('inf'):
                    last_idx = ed
        
        return max_len

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        last={1:-1}
        pro=1
        ans=0
        for i,c in enumerate(nums):
            pro=c*pro
            
            if pro>0:
                ans=max(i-last[1],ans)
                
            elif pro<0:
                if -1 in last:
                    ans=max(ans,i-last[-1])
                else:
                    last[-1]=i
            elif pro==0:
                pro=1
                last={}
                last[1]=i
          
        return ans
                
            
            


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        first_neg = None
        last_neg = None
        first_pos = None
        cum_prod = 1
        max_len = 0
        last_zero_idx = 0
        for idx, val in enumerate(nums):
            if val == 0:
                first_neg = None
                last_neg = None
                first_pos = None
                cum_prod = 1
                last_zero_idx = idx + 1
            else:
                cum_prod *= val
                if cum_prod > 0:
                    max_len = max(max_len, idx - last_zero_idx + 1)
                else:
                    if first_neg is None:
                        first_neg = idx
                    last_neg = idx
                    max_len = max(max_len, last_neg - first_neg)
        return max_len

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        i = 0
        negatives = [-1, -1]
        p = 1
        ans = 0
        for j, n in enumerate(nums):
            if not n:
                p = 1
                i = j + 1
                negatives = [-1, -1]
            else:
                p *= n
                if n < 0:
                    if negatives[0] < 0:
                        negatives[0] = j
                    negatives[1] = j
                if p > 0:
                    ans = max(ans, j - i + 1)
                else:
                    ans = max(ans, negatives[1] - i, j - negatives[0])
        return ans             
                        


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        longest = 0
        neg = len(nums)
        pos = -1
        
        prod = 1
        for i, n in enumerate(nums):
            if not n:
                neg = len(nums) 
                pos = i
                prod = 1
            else:
                prod *= n
                
                if prod < 0:
                    neg = min(neg, i)
                    longest = max(longest, i - neg)
                else:
                    longest = max(longest, i - pos)
            
        return longest

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:

        def helper(nums):
            if len(nums) == 0:
                return 0
            pre_prod = 1
            N = len(nums)
            first_neg = -1
            res = 0
            for i in range(N):
                pre_prod *= nums[i]
                if pre_prod > 0:
                    res = max(res, i + 1) 
                elif first_neg == -1 and pre_prod < 0:
                    first_neg = i
                elif pre_prod < 0:
                    res = max(res, i - first_neg) 
            return res

        num = []
        res = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                res = max(res, helper(num))
                num = []
            else:
                num.append(nums[i])      
        res = max(res, helper(num))
            
        return res

class Solution:
    def getMaxLen(self, A: List[int]) -> int:
        
        n = len(A)     
        lastZ = -1
        lastN = n
        cur = 1
        res = 0
        
        for i, a in enumerate(A):
            cur *= a
            
            if cur == 0:
                lastZ = i
                lastN = n
                cur = 1
            elif cur > 0:
                res = max(res, i - lastZ)
            else:
                lastN = min(lastN, i)
                res = max(res, i - lastN)
        
        return res

class Solution:
  def getMaxLen(self, nums: List[int]) -> int:
    max_len, start, product, first_minus_index = 0, 0, 1, -1
    for i, n in enumerate(nums):
      if n == 0:
        start, product, first_minus_index = i + 1, 1, -1
      else:
        if n < 0 and first_minus_index == -1:
          first_minus_index = i
        product *= n
        if n > 0:
          max_len = max(max_len, 1)
        if product > 0:
          max_len = max(max_len, i - start + 1)
        if product < 0 and first_minus_index != -1:
          max_len = max(max_len, i-first_minus_index)
    return max_len

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        s = 0
        fn = -1
        ln = -1
        cn = 0
        res = 0
        
        for i, v in enumerate(nums):
            if v == 0:
                end = i - 1
                if cn % 2 == 0:
                    res = max(res, end - s + 1)
                else:
                    res = max(res, end - fn, ln - s)
                s = i + 1
                fn = -1
                ln = -1
                cn = 0
            elif v < 0:
                if fn == -1:
                    fn = ln = i
                else:
                    ln = i
                cn += 1
        end = len(nums) - 1
        if cn % 2 == 0:
            res = max(res, end - s + 1)
        else:
            res = max(res, end - fn, ln - s)
        return res

class Solution:
    def getMaxLen(self, a: List[int]) -> int:
        n = len(a)
        ans = 0
        neg = -1 #position of last negative element
        zero = -1 #position of last zero
        cnt = 0 #number of negatives seen so far
        for i, x in enumerate(a):
            if x == 0:
                neg = zero = i
                cnt = 0
            elif x < 0:
                if neg == zero:
                    neg = i
                cnt += 1 
            if cnt % 2 == 0:
                ans = max(ans, i - zero)
            else:
                ans = max(ans, i - neg)
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        left_pos = 0
        left_neg = sys.maxsize
        ans = 0
        cp = 1
        for i, num in enumerate(nums):
            if num == 0:
                cp = 1
                left_pos = i + 1
                left_neg = sys.maxsize
            else:
                cp *= num
                # print(\"haha\", cp)
                if cp > 0:
                    ans = max(ans, i - left_pos + 1)
                    # print(\"hehe\", ans, num, cp)
                else:
                    ans = max(ans, i - left_neg)
                    # print(\"hehe\", ans, num, cp, left_neg)
                
                if cp < 0 and left_neg == sys.maxsize:
                    left_neg = i
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        a = [None] + nums
        n = len(a)
        pos = [0] * n
        neg = [0] * n
        for i in range(1, n):
            if a[i] > 0:
                pos[i] = pos[i - 1] + 1
                if neg[i - 1]:
                    neg[i] = neg[i - 1] + 1 # we can extend neg iff it exists
            elif a[i] < 0:
                if neg[i - 1]:
                    pos[i] = neg[i - 1] + 1 # same idea as above
                neg[i] = pos[i - 1] + 1
            else: # a[i] == 0
                pass
        return max(pos)

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
            n = len(nums)
            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 getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        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 getMaxLen(self, nums: List[int]) -> int:
        f = [0, 0]
        ans = 0
        for i in range(len(nums)):
            if nums[i] < 0:
                f = [f[1] + 1 if f[1] > 0 else 0, f[0] + 1]
            elif nums[i] > 0:
                f = [f[0] + 1, f[1] + 1 if f[1] > 0 else 0]
            else:
                f = [0, 0]
            ans = max(ans, f[0])
        #print(f)
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        ans = 0
        pos, neg = 0, 0
        for i in range(len(nums)):
            if nums[i] > 0:
                pos = pos + 1
                neg = neg + 1 if neg > 0 else 0
            elif nums[i] < 0:
                pos, neg = neg+1 if neg > 0 else 0, pos+1
            else:
                pos, neg = 0, 0
            ans = max(ans, pos)
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        pos = [0 for _ in range(n)]
        neg = [0 for _ in range(n)]
        if nums[0] > 0:
            pos[0] = 1 
        if nums[0] < 0:
            neg[0] = 1 
        res = pos[0]
        for i in range(1, n):
            if nums[i] > 0:
                pos[i] = pos[i - 1] + 1
                neg[i] = neg[i - 1] + 1 if neg[i - 1] > 0 else 0
            elif nums[i] < 0:
                pos[i] = neg[i - 1] + 1 if neg[i - 1] > 0 else 0
                neg[i] = pos[i - 1] + 1
            res = max(res, pos[i])
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        # 类似于前缀和 看区间
        # sums 记录从第一个不是0 开始 到当前index的正负情况
        # 如果sums 是负的话，看之前有没有negative 的index
        # 如果有，减去上一个negative 的index， 上一个negative index 到 当前index 整个区间就变成正的了
        # 如果没有，记录当前的index 更新negative
        # 如果sums 是正的话， 直接更新，当前idnex 减去 上一个0 的位置，或者 初始化 -1
        # 如果遇到0，全部初始化 重新计算
        positive_index = - 1
        negative_index = - 1
        sums = 1
        result = 0
        for i in range(len(nums)):
            if sums * nums[i] < 0:
                sums = -1
            elif sums * nums[i] > 0:
                sums = 1
            
            if nums[i] == 0:
                positive_index = i
                negative_index = -1
                sums = 1
            elif sums > 0:
                result = max(result, i - positive_index)
            else:
                if negative_index == -1:
                    negative_index = i
                else:
                    result = max(result, i - negative_index)
                    print(result)
        return result

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        N =len(nums)
        ans = 0
        i = j = 0
        while i<N:
            if nums[i] == 0:
                i+= 1
                continue
            j = i
            while j < N and nums[j]:
                j+= 1
            negs = 0
            firstneg = lastneg = None
            for k in range(i,j ):
                if nums[k] <0:
                    negs += 1
                    if firstneg is None:
                        firstneg = k
                    lastneg = k
            if negs % 2 ==0:
                ans = max(ans, j-i)
            else:
                ans = max(ans, firstneg -i, j-i-1-(firstneg-i))
                ans = max(ans, lastneg -i, j-i-1-(lastneg-i))
            i = j 
        return ans


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        result = 0
        
        for r in [list(range(0, len(nums))), list(range(len(nums)-1, -1, -1))]:
            cur_len = 0
            cur_sign = 1
            for i in r:
                if nums[i] > 0:
                    cur_len += 1
                    result = max(result, cur_sign * cur_len)
                elif nums[i] == 0:
                    cur_len = 0
                    cur_sign = 1
                else: # < 0
                    cur_len += 1
                    cur_sign = -cur_sign
                    result = max(result, cur_sign * cur_len)

        return result


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        first_neg = -1
        last_neg = -1
        pos = True
        start = 0
        best = 0
        n = len(nums)
        for i, num in enumerate(nums):
            if num == 0:
                if pos:
                    best = max(best, i - start)
                else:
                    if first_neg >= start:
                        best = max(best, i - first_neg - 1, last_neg - start)
                start = i + 1
                pos = True
            elif num < 0:
                last_neg = i
                if first_neg < start:
                    first_neg = i
                pos = not pos
        if pos:
            best = max(best, n - start)
        else:
            if first_neg >= start:
                best = max(best, n - first_neg - 1, last_neg - start)
        return best


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        pos = [0] * n
        neg = [0] * n
        
        if nums[0] > 0:
            pos[0] = 1
            
        if nums[0] < 0:
            neg[0] = 1
        
        ans = pos[0]
        
        for i in range(1,len(nums)):
            if nums[i] > 0:
                neg[i] = 1 + neg[i - 1] if neg[i - 1] > 0 else 0
                pos[i] = 1 + pos[i - 1]
                 
            if 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 getMaxLen(self, nums: List[int]) -> int:
        result = 0
        cur_len = 0
        cur_sign = 1
        
        for i in range(0, len(nums)):
            if nums[i] > 0:
                cur_len += 1
                result = max(result, cur_sign * cur_len)
            elif nums[i] == 0:
                cur_len = 0
                cur_sign = 1
            else: # < 0
                cur_len += 1
                cur_sign = -cur_sign
                result = max(result, cur_sign * cur_len)

        cur_len = 0
        cur_sign = 1
        for i in range(len(nums)-1, -1, -1):
            if nums[i] > 0:
                cur_len += 1
                result = max(result, cur_sign * cur_len)
            elif nums[i] == 0:
                cur_len = 0
                cur_sign = 1
            else: # < 0
                cur_len += 1
                cur_sign = -cur_sign
                result = max(result, cur_sign * cur_len)

        return result


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        #------------------------------
        def helper(array):
            if len(array)==0:
                return 0
            
            result=0
            pos=0
            neg=0
            
            for n in array:
                if n>0:
                    pos, neg = pos+1, neg+1 if neg>0 else 0
                if n<0:
                    pos, neg = neg+1 if neg>0 else 0, pos+1 
                
                result=max(result,pos)
            return result
        #------------------------------
    
        arrays=[]
        subarray=[]
       
        for n in nums:
            if n==0:
                idx=0
                arrays.append(subarray)
                subarray=[]
                continue
            subarray.append(n)
        if len(subarray)>0:
            arrays.append(subarray)
            
        maxlen=0
        for i,array in enumerate(arrays):
            maxlen=max(maxlen,helper(array))
        
        return maxlen
        


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        start = 0
        end = 0
        count_negative = 0
        max_len = 0
        while end < len(nums):
            if nums[end] == 0:
                if count_negative % 2 != 0:
                    while nums[start] > 0:
                        start += 1
                    max_len = max(max_len, end - start - 1)
                start = end = end + 1
                count_negative = 0
            else:
                if nums[end] < 0:
                    count_negative += 1
                if count_negative % 2 == 0:
                    max_len = max(max_len, end - start + 1)
                if end == len(nums)-1 and count_negative % 2 == 1:
                    while nums[start] > 0:
                        start += 1
                    max_len = max(max_len, end - start)
                end += 1                  
        return max_len

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        count_of_negative = 0
        start = 0
        max_length = 0 
        
        def evaluate_sub_array(begin, end, count_of_negative):
            if count_of_negative % 2 == 0:
                return end-begin+1
            else:
                first_negative = len(nums)
                last_negative = -1
                for i in range(begin,end+1):
                    if nums[i] < 0:
                        if first_negative == len(nums):
                            first_negative = i
                            last_negative = i
                        else:
                            last_negative = i
            return max(end - first_negative, last_negative - begin)
            
        start = 0
        array = []
        count_of_negative = 0
        for index in range(len(nums)):
            if nums[index] <0:
                count_of_negative+=1
            if nums[index] == 0:
                array.append(evaluate_sub_array(start, index-1, count_of_negative))
                count_of_negative = 0
                start = index+1
        array.append(evaluate_sub_array(start, len(nums)-1, count_of_negative))
        return max(array)


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        pos, neg = 0, 0
        if nums[0] > 0: pos = 1
        if nums[0] < 0: neg = 1
        ans = pos
        for i in range(1, n):
            if nums[i] > 0:
                pos = 1 + pos
                neg = 1 + neg if neg > 0 else 0
            elif nums[i] < 0:
                pos, neg = 1 + neg if neg > 0 else 0, 1 + pos
            else:
                pos, neg = 0, 0
            ans = max(ans, pos)
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        dic={1:-1}
        temp=1
        res=0
        for i in range(len(nums)):
            if nums[i]==0:
                dic={1:i}
                temp=1
                continue
            if nums[i]<0:
                temp=-temp
            if not dic.get(temp) is None:
                res=max(res,i-dic[temp])
            else:
                dic[temp]=i
                
            
            
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        #reduce to simpler problem:
        # if all elems are positive, then entire array is sol as long as thy're >= 1
        
        # an even number of negative vals still gives a pos result
        
        # insight: we don't care what the values actually are , just whether they're pos, 0 , or neg
        # insight: we can't include a zero, since the prod becomes 0, and 0 isn't +ve
        
        # idea: start with first char, if you hit zero, stop, if not, keep going, and track latest position of even number of negatives.
        
        # also start at other negative vals, and positive vals after zero.
        
#         cur_max = 0
        
#         last_even_neg = -1
        
#         for i, n in enumerate(nums):
#             if n == 0:
#                 if last_even_neg >
#             if i == 0 or (i and nums[i-1] == 0)

        # first, split the array into segment to get rid of zeros.
        
        def max_len(nums):
            negs = [i for i, x in enumerate(nums) if x < 0]
            n = len(nums)
            
            if len(negs) % 2 == 0:  # even num of odd nums, whose product is pos
                return n
            else:  # at least one neg val
                return max(n - (negs[0] + 1), negs[-1])  # exclude either left or right most neg val
            
        
        from copy import deepcopy
        chunks = []
        
        chunk = []
        for x in nums:
            if x == 0 and chunk:  # see a zero, add a new segment
                chunks.append(deepcopy(chunk))
                chunk.clear()
            elif x:
                chunk.append(x)
        chunks.append(chunk)
        print(chunks)
                
        return max(map(max_len, chunks))

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        m=0
        neg=0
        pos=0
        positiveBeforeFirstNeg=0
        pos2=0
        for i in nums:
            if(i==0):
                if(neg>0 and neg%2!=0):
                    neg-=1
                if(positiveBeforeFirstNeg<pos2 and neg>2):
                    pos-=positiveBeforeFirstNeg
                    pos+=pos2
                m=max(max(pos,pos2)+neg,m)
                neg,pos,pos2=0,0,0
            elif(i<0):
                if(neg==0):
                    positiveBeforeFirstNeg=pos
                neg+=1
                if(neg%2==0):
                    pos+=pos2
                    pos2=0
            else:
                if(neg%2!=0):
                    pos2+=1
                else:
                    pos+=1
        if(positiveBeforeFirstNeg<pos2 and neg>2):
            pos-=positiveBeforeFirstNeg
            pos+=pos2
        if(neg>0 and neg%2!=0):
            neg-=1
        m=max(max(pos,pos2)+neg,m)     
        return m

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        # encouter 0 reset it as 0
        # how many -1 in the left, if is even, update the  longest length O(n) cur_poistion - 0_position
        
        # [1,-2,-3,4] => [0, 1, 2, 2] => 4
        # [0,1,-2,-3,-4] => [0, 0, 1, 2, 3] => 3
        # [-1,-2,-3,0,1] => [1, 2, 3, 0, 0] => 2
        # [-1,2] => [1, 1] => 1 (consider if itself > 0, 1)
        # [1,2,3,5,-6,4,0,10] => [0, 0, 0, 0, 1, 1, 0, 1] => 4
        # [0, 0 ,0 ,0] => [0, 0, 0, 0] => 0 (consider if itself == 0, 0)
        
        carry_len = 0
        left_neg = 0
        max_len = 0
        str_ptr = -1
        for idx, n in enumerate(nums):
            if n < 0 :left_neg += 1 
            carry_len += 1
            if n == 0: 
                max_len = max(max_len, 0)
                carry_len = 0
                left_neg = 0
            else:
                max_len = max(max_len, 1 if n > 0 else 0, idx - str_ptr -1, carry_len if left_neg % 2 == 0 else 0)
            if left_neg == 0: 
                str_ptr = idx

        return max_len

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        start, curnegcnt, res, fnegpos, lnegpos = 0, 0, 0, 0, 0
        flag = True
        i, j = 0, len(nums)
        while i < j:
            if nums[i] == 0:
                flag = True
                i += 1
                start = i
                curnegcnt = 0
                continue
            if nums[i] < 0:
                if flag:
                    flag = False
                    fnegpos = i
                lnegpos = i
                curnegcnt += 1
            if curnegcnt == 0 or curnegcnt % 2 == 0:
                res = max(res, (i - start) + 1)
            else:

                res = max(res, (lnegpos ) - start, i - (fnegpos ))
            i += 1
        return res
                
                
    


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        #每次maintain，到之前为止，正的有多长，负的有多长，然后maintain max len
        pos,neg = 0,0
        asr = 0
        for num in nums:
            if num == 0:
                pos,neg = 0,0
            elif num > 0:
                pos+=1
                neg = neg + 1 if neg else 0
            else:
                n_pos = neg + 1 if neg else 0
                n_neg = pos + 1 if pos else 1
                pos,neg = n_pos,n_neg
            asr = max(asr,pos)
            #print(pos,neg)
        return asr

# 1567. Maximum Length of Subarray With Positive Product

def sgn (n):
    if n > 0:
        return +1
    elif n < 0:
        return -1
    else:
        return 0

def split_0 (arr):
    arr_buffer = []
    for elem in arr:
        if elem != 0:
            arr_buffer.append (elem)
        else:
            yield arr_buffer
            arr_buffer = []
    assert len (arr_buffer) == 0

def partial_products (arr):
    prod = 1
    yield prod
    for elem in arr:
        prod *= elem
        yield prod

def get_subarr_max_len (arr):
    # zero-free
    first_index = {}
    max_len = 0
    for (i, prod) in enumerate (partial_products (arr)):
        first_index.setdefault (prod, i)
        max_len = max (max_len, i - first_index[prod])
    return max_len

def get_max_len (arr):
    arr = [sgn (x) for x in arr]
    arr.append (0)

    if len (arr) == 0:
        return 0

    return max (get_subarr_max_len (subarr) for subarr in split_0 (arr))

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        return get_max_len(nums)

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        f = [[0, 0] for _ in range(len(nums) + 1)]
        for i in range(len(nums)):
            if nums[i] < 0:
                f[i+1] = [f[i][1] + 1 if f[i][1] > 0 else 0, f[i][0] + 1]
            elif nums[i] > 0:
                f[i+1] = [f[i][0] + 1, f[i][1] + 1 if f[i][1] > 0 else 0]
        #print(f)
        return max(x[0] for x in f)

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        dp_pos = [0] * (n+1)
        dp_neg = [0] * (n+1)

        result = 0
        for i in range(1, n+1):
            if nums[i-1] == 0:
                dp_pos[i] = 0
                dp_neg[i] = 0
            elif nums[i-1] > 0:
                dp_pos[i] = 1 + dp_pos[i-1]

                if dp_neg[i-1] > 0:
                    dp_neg[i] = 1 + dp_neg[i-1]
                else:
                    dp_neg[i] = 0
            else:
                if dp_neg[i-1] > 0:
                    dp_pos[i] = 1 + dp_neg[i-1]
                else:
                    dp_pos[i] = 0

                dp_neg[i] = 1 + dp_pos[i-1]

            result = max(result, dp_pos[i])

        return result


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        if not n:
            return -1
        pos = 0
        neg = 0
        answer = 0
        for num in nums:
            if num == 0:
                answer = max(answer, pos)
                pos = neg = 0
                continue
            if num > 0:
                pos += 1
                neg += 1 if neg else 0
            else:
                orig_pos = pos
                pos = neg+1 if neg else 0
                neg = (orig_pos + 1) if orig_pos else 1
            answer = max(answer, pos)
        return answer

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        dct = {0:-1}
        
        count = 0
        res = 0
        for i,num in enumerate(nums):
            if num <0: 
                count +=1
                # print(num,count,i)
                dct[count]=i
                
            elif num == 0:
                dct = {0:i}
                count = 0
            if count %2 == 0:
                res = max(res,i-dct[0])
                
            else:
                t1 = i-dct[1]
                t2= 0
                if num < 0:
                    t2 = i-1-dct[0]
                res = max(res,max(t1,t2))
            # print(dct,res)
        return res
            
            


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        if nums[-1] != 0:
            nums.append(0)
        n = len(nums)
        first_0 = -1
        last_0 = -1
        cnt_neg = 0
        first_neg = -1
        last_neg = -1
        res = 0
        # print(nums)
        for i, e in enumerate(nums):
            if e < 0:
                cnt_neg += 1
                if first_neg == -1:
                    first_neg = i
                last_neg = i
            elif e == 0:
                # print(cnt_neg)
                last_0 = i
                if cnt_neg % 2 == 0:
                    res = max(res, last_0-first_0-1)
                else:
                    res = max(res, last_neg-first_0-1, last_0-first_neg-1)
                    # print((first_0, last_0, first_neg, last_neg, res))
                cnt_neg = 0
                first_0 = last_0
                first_neg = -1
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        a = 0
        p = 0
        n = 0
        r = -1

        for x in nums:
            p, n, r = (
                (x < 0) * p + (x > 0) * (p + 1),
                (x < 0) * (n + 1) + (x > 0) * n,
                (x < 0) * (r < 0) * p + (x < 0) * (r >= 0) * r + (x > 0) * r - (x == 0)
            )
            
            a = max(a, p + n - (n % 2) * (r + 1))
                   
        return a

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        # get the next zero or end
        # get the last idx of negative before zero and end
        # get how many negative numbers
        
        next_zero_or_end=[0]*(len(nums)+1)
        next_idx=len(nums)
        last_negative=[0]*(len(nums)+1)
        negative_idx=None
        state=0
        for i in range(len(nums)-1,-1,-1):
            num=nums[i]
            if num==0:
                next_idx=i
                state=0
            next_zero_or_end[i]=next_idx
            if state==0 and num<0:
                negative_idx=i
                state=1
            last_negative[i]=negative_idx
                
        ne_nums=[0] * (len(nums)+1)
        for i,num in enumerate(nums):
            ne_nums[i]=ne_nums[i-1]+(1 if num<0 else 0)
        res=0
        for i in range(len(nums)):
            if nums[i]==0:
                continue
            j=next_zero_or_end[i]-1
            if (ne_nums[j]-ne_nums[i-1])%2==0:
                res=max(res,(j-i+1))
            else:
                j=last_negative[i]-1
                res=max(res,(j-i+1))
        return res


class Node:
    def __init__(self, size):
        self.size = size
        self.left = None
        self.right = None
        


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        nodes = []
        roots = []
        
        curr_size = 0
        prev = None
        
        for i in range(len(nums)):
            if nums[i] > 0:
                curr_size += 1
            else:
                node = Node(curr_size)
                nodes.append(node)
                if prev:
                    prev.right = node
                    node.left = prev
                else:
                    roots.append(node)
                if nums[i] != 0:
                    prev = node
                else:
                    prev = None
                curr_size = 0
                    
        node = Node(curr_size)
        if prev:
            prev.right = node
            node.left = prev
        else:
            roots.append(node)
                
        # t_node = roots[0]
        # while t_node:
        #     print(t_node.size)
        #     t_node = t_node.right
        
        longest = 0
        for node in roots:
            first_count = node.size
            second_count = 0 if not node.right else node.right.size
            
            curr_node = node.right.right if node.right else None
            
            ind = 0
            
            while curr_node:
                if ind == 0:
                    first_count += curr_node.size + curr_node.left.size + 2
                    ind = 1
                else:
                    second_count += curr_node.size + curr_node.left.size + 2
                    ind = 0
                curr_node = curr_node.right
                
            # print(first_count)
            # print(second_count)
            longest = max(longest, first_count, second_count)
            
        return longest
                    
            


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        pos = [0 for _ in range(len(nums))] # pos[i] is number of consecutive numbers with pos product up to i
        neg = [0 for _ in range(len(nums))] # neg[i] is number of consecutive numbers with neg product up to i
        if nums[0] > 0 :
            pos[0] = 1
        elif nums[0] < 0:
            neg[0] = 1
            
        out = pos[0]
        for i in range(1, len(nums)):
            if nums[i] > 0:
                pos[i] = 1 + pos[i - 1] 
                neg[i] = 1 + neg[i - 1] if neg[i - 1] else 0
            elif nums[i] < 0:
                pos[i] = 1 + neg[i - 1] if neg[i - 1] else 0
                neg[i] = 1 + pos[i - 1]
            out = max(out, pos[i])
        
        return out

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        def getMaxLenNonzero(arr):
            neg = []
            for i, num in enumerate(arr):
                if num < 0:
                    neg.append(i)
            if len(neg) % 2 == 0:
                return len(arr)
            if len(neg) == 1:
                return max(neg[0], len(arr) - neg[-1] - 1)
            return max(neg[-1], len(arr) - neg[0] - 1)
    
        currArr = []
        ans = 0
        for num in nums:
            if num != 0:
                currArr.append(num)
            else:
                ans = max(ans, getMaxLenNonzero(currArr))
                currArr = []
        if currArr:
            ans = max(ans, getMaxLenNonzero(currArr))

        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        for i in range(len(dp)):
            dp[i] = [0,0]
        
        ans = 0
        for i, v in enumerate(nums):
            if v > 0:
                dp[i][0] = 1 + dp[i-1][0]
                if dp[i-1][1]: dp[i][1] = 1 + dp[i-1][1]
            if v < 0:
                if dp[i-1][1]:
                    dp[i][0] = 1 + dp[i-1][1]
                dp[i][1] = 1 + dp[i-1][0]
            ans = max(ans, dp[i][0])
        return ans
                    
                
                
                
            
                


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        ans = pos = neg = 0
        for x in nums: 
            if x > 0: pos, neg = 1 + pos, 1 + neg if neg else 0
            elif x < 0: pos, neg = 1 + neg if neg else 0, 1 + pos
            else: pos = neg = 0 # reset 
            ans = max(ans, pos)
        return ans
            


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        A = nums
        n = len(A)
        dp = [[0,0] for i in range(n+1)]
        
        max_len = 0
        for i in range(1,n+1):
            if A[i-1] > 0:
                dp[i][0] = dp[i-1][0]+1
                dp[i][1] = dp[i-1][1]+1 if dp[i-1][1] != 0 else 0
            elif A[i-1] < 0:
                dp[i][0] = dp[i-1][1]+1 if dp[i-1][1] != 0 else 0
                dp[i][1] = dp[i-1][0]+1
            else:
                dp[i][0] = 0
                dp[i][1] = 0
            max_len = max(max_len, dp[i][0])
        # print(dp)
        
        return max_len

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        ret=0
        total=0
        acc=1
        start=-1
        first=-1
        last=0
        for i in range(len(nums)):
            if nums[i]==0:
                if acc>0:
                    ret=max(total,ret)
                else:
                    ret=max(ret,first-1,total-first,last-1,total-last)
                start=i
                acc=1
                total=0
                first=-1
                last=0
            else:
                total+=1
                acc=acc*(1 if nums[i]>0 else -1)
                if nums[i]<0:
                    if first==-1:
                        first=i-start
                    last=0
                last+=1
        if acc>0:
            ret=max(total,ret)
        else:
            ret=max(ret,first-1,total-first,last-1,total-last)
        return ret

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        listt = []
        a = -1
        for i in range(len(nums)):
            if nums[i] == 0:
                listt.append(nums[a + 1:i])
                a = i
        listt.append(nums[a + 1:])
        while [] in listt:
            listt.remove([])
        if listt==[]:
            return 0
        recordlist = {}
        for i in range(len(listt)):
            firstneg=-1
            begneg=-1
            recordlist[i]=0
            for m in range(len(listt[i])):
                if listt[i][m]<0 and firstneg==-1:
                    firstneg = m
                    if begneg==-1:
                        begneg=m
                    continue
                if listt[i][m]<0 and firstneg!=-1:
                    firstneg=-1
            if firstneg==-1:
                recordlist[i]=len(listt[i])
            else:
                recordlist[i]=max([firstneg,len(listt[i])-firstneg-1,begneg,len(listt[i])-begneg-1])
        m=[]
        for i in list(recordlist.values()):
            m.append(i)
        return max(m)


class Solution:
    #Any subarray containing a zero must be broken into seperate subarrays either side of the zero
    #Any subarr with an even number of negatives can be counted in its entirety
    #For a subarr with an odd number of negatives, the largest subarray excluding either the left or rightmost negative number can be taken instead

    def getMaxLen(self, nums: List[int]) -> int:
        #Simplify array to +-1
        for i in nums:
            if i > 0:
                i = 1
            elif i < 0:
                i = -1
                
        arrays = []
        end = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                arrays.append(nums[end:i])
                end = i + 1
        arrays.append(nums[end:])
        
        #print(arrays)
        maximum = 0
        for arr in arrays:
            maxi = 0
            neg = 0
            first = -1
            for i in range(len(arr)):
                if arr[i] < 0:
                    neg += 1
                    if first == -1:
                        first = i + 1
                    last = i
            if neg % 2 == 0:
                maxi = len(arr)
            else:
                #Length of sub a (missing first)
                subA = len(arr) - first    
                #Length of sub b (missing last)
                subB = last
                maxi = max(subA, subB)
            #print(arr, maxi)
            maximum = max(maximum, maxi)
            
        
        return maximum
                
            


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        def helper(nums):
            result = 0

            positiveSoFar = 0
            negativeSoFar = 0

            for i in range(len(nums)):
                if nums[i] == 0:
                    positiveSoFar = 0
                    negativeSoFar = 0
                elif nums[i] > 0 :
                    positiveSoFar += 1
                    if negativeSoFar > 0:
                        negativeSoFar += 1

                elif nums[i] < 0:
                    if negativeSoFar > 0:
                        positiveSoFar = max(negativeSoFar, positiveSoFar) +1
                        negativeSoFar = 0
                    else:
                        negativeSoFar = positiveSoFar + 1
                        positiveSoFar = 0

                result = max(result, positiveSoFar)
            return result
        
        # scan from left and scan from right
        return max(helper(nums), helper(nums[::-1]))
        


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        dp = []
        for num in nums:
            if num == 0:
                dp.append(0)
            elif num > 0:
                dp.append(1)
            else:
                dp.append(-1)
        for i in range(1, len(dp)):
            if dp[i - 1] == 0:
                continue
            else:
                dp[i] *= dp[i - 1]
        print(dp)
        dic = {}
        res = 0
        zero = -1
        for i,num in enumerate(dp):
            if num > 0:
                if 1 not in dic:
                    res = max(res,i  - zero)
                    dic[1] = i
                else:
                    res = max(res, i - dic[1] + 1, i - zero)
            elif num == 0:
                dic = {}
                zero = i
            else:
                if -1 not in dic:
                    dic[-1] = i
                else:
                    res = max(res, i  - dic[-1])
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        pos, neg = 0, 0
        if nums[0]>0: pos = 1
        if nums[0]<0: neg = 1
        ans = pos
        for i in range(1, len(nums)):
            if nums[i] > 0:
                pos, neg = pos+1, neg+1 if neg else 0
            elif nums[i] < 0:
                pos, neg = neg+1 if neg else 0, pos+1
            else:
                pos, neg = 0, 0
            ans = max(ans,pos)
            
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        
        def helper(nums):
            result = 1 if nums[0] > 0 else 0

            positiveSoFar = 1 if nums[0] > 0 else 0
            negativeSoFar = 1 if nums[0] < 0 else 0


            for i in range(1, len(nums)):
                if nums[i] == 0:
                    positiveSoFar = 0
                    negativeSoFar = 0
                elif nums[i] > 0 :
                    positiveSoFar += 1
                    if negativeSoFar > 0:
                        negativeSoFar += 1

                elif nums[i] < 0:
                    if negativeSoFar > 0:
                        positiveSoFar = max(negativeSoFar, positiveSoFar) +1
                        negativeSoFar = 0
                    else:
                        negativeSoFar = positiveSoFar + 1
                        positiveSoFar = 0

                result = max(result, positiveSoFar)
            return result
        
        
        return max(helper(nums), helper(nums[::-1]))
        


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        numPos, numNeg, res = 0, 0, 0
        
        for i in range(len(nums)):
            if nums[i] > 0:
                numPos += 1
                if numNeg > 0: numNeg += 1
            elif nums[i] < 0:
                numPosTmp, numNegTmp = numPos, numNeg
                if numPosTmp > 0:
                    numNeg = numPosTmp + 1
                else:
                    numNeg = 1
                if numNegTmp > 0:
                    numPos = numNegTmp + 1
                else:
                    numPos = 0
            else:
                numNeg = 0
                numPos = 0
            res = max(res, numPos)
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        splittedArrays = []
        
        currentArray = []
        negCount = 0
        for num in nums:
            if num == 0:
                if len(currentArray) > 0:
                    splittedArrays.append((currentArray, negCount))
                currentArray = []
                negCount = 0
            else:
                currentArray.append(num)
                negCount += 1 if num < 0 else 0
        
        if len(currentArray) > 0:
            splittedArrays.append((currentArray, negCount))
        
        if not splittedArrays:
            return 0
        
        maxLength = 0
        for splittedArray, negCount in splittedArrays:
            if negCount % 2 == 0:
                maxLength = max(maxLength, len(splittedArray))
            else:
                removedNums = 0
                i = 0
                while splittedArray[i] > 0:
                    removedNums += 1
                    i += 1
                maxLength = max(maxLength, len(splittedArray) - removedNums - 1)
                
                removedNums = 0
                i = len(splittedArray) - 1
                while splittedArray[i] > 0:
                    removedNums += 1
                    i -= 1
                maxLength = max(maxLength, len(splittedArray) - removedNums - 1)
        
        return maxLength

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        pos = [0] * n
        neg = [0] * n
        
        if nums[0] < 0:
            neg[0] = 1
        elif nums[0] > 0:
            pos[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 getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        l = -1
        neg_num = 0
        result = 0
        for i in range(n):
            if (nums[i] == 0):
                while (neg_num % 2):
                    if (nums[l + 1] < 0):
                        neg_num -= 1
                    l += 1
                # print(i, l)
                result = max(result, i - l - 1)
                l = i
                count = 0
            elif (nums[i] < 0):
                neg_num += 1
            if (neg_num % 2 == 0):
                result = max(result, i - l)
        while (neg_num % 2) and (l < n - 1):
            if (nums[l + 1] < 0):
                neg_num -= 1
            l += 1
        # print(l)
        result = max(result, n - 1 - l)
        return result

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        size = len(nums)
        if size == 1:
            return 0 if nums[0] < 0 else 1
        
        
        start = 0
        end = 0
        
        longest = 0
        
        while end < size:
        
            numNeg = 0
            leftNeg = -1
            rightNeg = -1
        
            while end < size and not nums[end] == 0:
                if nums[end] < 0:
                    
                    numNeg += 1
                    rightNeg = end
                    
                    if leftNeg == -1:
                        leftNeg = end
                        
                end += 1
                
            if numNeg % 2 == 0:
                longest = max(longest, end - start)
            else:
                longest = max(longest, end - rightNeg - 1, rightNeg - start, end - leftNeg - 1, leftNeg - start)
                
                
            end += 1
            start = end
            
        return longest

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        pos, neg = -1, n
        c = 1
        ret = 0
        for i, j in enumerate(nums):
            if j == 0:
                pos, neg = i, n
                c = 1
                continue
            if j > 0:
                pass
            else:
                c *= -1
            if c == 1:
                ret = max(ret, i - pos)
            else:
                ret = max(ret, i - neg)
                neg = min(neg, i)
        return ret

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        dp = [[0]*2 for _ in range(len(nums))]
        dp[0][0] = nums[0] > 0
        dp[0][1] = nums[0] < 0
        ret = dp[0][0]
        for i in range(1,len(nums)):
            if nums[i] == 0:
                continue
            if nums[i] > 0:
                dp[i][0] = dp[i-1][0] + 1
                dp[i][1] = 0 if not dp[i-1][1] else dp[i-1][1] + 1
            else:
                dp[i][0] = 0 if not dp[i-1][1] else dp[i-1][1] + 1
                dp[i][1] = dp[i-1][0] + 1
            ret = max(ret,dp[i][0])
        return int(ret)



# dp[i][0] : max length of subarray ending with index i With positive product   
# dp[i][1] : max length of subarray ending with index i With negative product 


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        dp = [[0,0] for _ in range(len(nums))]
        res = 0
        if nums[0] > 0:
            dp[0][0] = 1
        elif nums[0] < 0:
            dp[0][1] = 1
        #print(dp)
        res = max(res, dp[0][0])
        for idx in range(1, len(nums)):
            if nums[idx] == 0:
                dp[idx][0], dp[idx][1] = 0, 0
            elif nums[idx] > 0:
                dp[idx][0] = dp[idx-1][0] + 1
                if dp[idx-1][1] > 0:
                    dp[idx][1] = dp[idx-1][1] + 1
                res = max(dp[idx][0], res)
            
            elif nums[idx] < 0:
                dp[idx][1] = dp[idx-1][0]+1
                if dp[idx-1][1] > 0:
                    dp[idx][0] = dp[idx-1][1]+1
                res = max(res, dp[idx][0])
                
        #print(dp)
        return res



'''
class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        diction = {}
        diction[\"pos\"], diction[\"neg\"] = 0, 0
        prevpos, prevneg = 0, 0
        res = 0
        for num in nums:
            if num == 0:
                diction[\"pos\"], diction[\"neg\"] = 0, 0
                prevpos, prevneg = 0, 0
            elif num > 0:
                diction[\"pos\"] += 1
                if diction[\"neg\"] % 2 == 0:
                    res = max(res, diction[\"pos\"]+diction[\"neg\"]+prevpos)
                    print(num, res)
                else:
                    res = max(res, diction[\"pos\"], prevpos)
        
            elif num < 0:
                diction[\"neg\"] += 1
                print(\"neg\", num, diction[\"neg\"], diction[\"pos\"], prevpos)
                if diction[\"neg\"] % 2 == 1:
                    res = max(res, diction[\"pos\"])
                    prevpos += diction[\"pos\"]
                    diction[\"pos\"] = 0
                else:
                    res = max(res, diction[\"pos\"]+diction[\"neg\"]+prevpos)
                    prevpos = diction[\"neg\"] + diction[\"pos\"] + prevpos
                    diction[\"neg\"] = 0
                    diction[\"pos\"] = 0
                    
        print(res)
        return res
'''

        
'''
        diction = {}
        diction[\"pos\"], diction[\"neg\"] = 0, 0
        res = 0
        for num in nums:
            if num == 0:
                diction[\"pos\"], diction[\"neg\"] = 0, 0
            elif num > 0:
                diction[\"pos\"] += 1
                if diction[\"neg\"] % 2 == 0:
                    res = max(res, diction[\"pos\"]+diction[\"neg\"])
            elif num < 0:
                diction[\"neg\"] += 1
                
                if diction[\"neg\"] % 2 == 1:
                    res = max(res, diction[\"pos\"]+diction[\"neg\"]-1)
                else:
                    res = max(res, diction[\"pos\"]+diction[\"neg\"])
                
        print(res)
        
        return res
        

'''


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        # \"pos\", \"neg\" represent longest consecutive numbers ending with nums[i] forming a positive/negative product.

        n = len(nums)
        pos, neg = 0, 0
        if nums[0] > 0: pos = 1
        if nums[0] < 0: neg = 1
        ans = pos
        for i in range(1, n):
            if nums[i] > 0:
                pos = 1 + pos
                neg = 1 + neg if neg > 0 else 0
            elif nums[i] < 0:
                pre_pos, pre_neg = pos, neg
                pos = 1 + pre_neg if pre_neg > 0 else 0
                neg = 1 + pre_pos
            else:
                pos, neg = 0, 0
            ans = max(ans, pos)
        return ans
    
        # nums.append(0)
        # start = -1
        # i = 0
        # firstn = -1
        # maxl = 0
        # nneg = 0
        # while i<len(nums):
        #     if nums[i]<0:
        #         nneg += 1
        #         if firstn<0: firstn = i
        #         lastn = i
        #     elif nums[i] == 0:
        #         if nneg%2 == 0:
        #             maxl = max(maxl,i-start-1)
        #         else:
        #             maxl = max([maxl,lastn-start-1,i-firstn-1])
        #         start = i
        #         nneg = 0
        #         firstn = -1
        #     i += 1
        # return maxl


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        # dp[i]: max length of pos subarray ends at i
        l = len(nums)
        pdp = [0] * l
        ndp = [0] * l
        pdp[0] = 1 if nums[0] > 0 else 0
        ndp[0] = 1 if nums[0] < 0 else 0
        b = pdp[0]
        for i in range(1, l):
            n = nums[i]
            if n > 0:
                pdp[i] = max(pdp[i - 1] + 1, 1)
                ndp[i] = ndp[i - 1] + 1 if ndp[i - 1] != 0 else 0
            elif n < 0:
                ndp[i] = max(pdp[i - 1] + 1, 1)
                pdp[i] = ndp[i - 1] + 1 if ndp[i - 1] != 0 else 0
            else:
                pdp[i] = 0
                ndp[i] = 0
            b = max(b, pdp[i])
            
        return b


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        dp = [[0] * 2 for _ in range(len(nums))]
        if nums[0] < 0:
            dp[0][1] = 1
        if nums[0] > 0:
            dp[0][0] = 1
            
        res = dp[0][0]
            
        for i, num in enumerate(nums):
            if i and num < 0:
                dp[i][1] = dp[i-1][0] + 1
                if dp[i-1][1]:
                    dp[i][0] = dp[i-1][1] + 1
            if i and num > 0:
                dp[i][0] = dp[i-1][0] + 1
                if dp[i-1][1]:
                    dp[i][1] = dp[i-1][1] + 1
            res = max(res, dp[i][0])
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        if not nums:
            return 0
        cur_pos_product_len = 1 if nums[0] > 0 else 0
        cur_neg_product_len = 1 if nums[0] < 0 else 0
        max_len = cur_pos_product_len        
        
        for i in range(1, len(nums)):
            if nums[i] > 0:
                cur_pos_product_len += 1
                cur_neg_product_len = cur_neg_product_len + 1 if cur_neg_product_len > 0 else 0
            elif nums[i] < 0:
                temp = cur_pos_product_len
                cur_pos_product_len = cur_neg_product_len + 1 if cur_neg_product_len > 0 else 0
                cur_neg_product_len = temp + 1
            else:
                cur_pos_product_len = 0
                cur_neg_product_len = 0
            max_len = max(max_len, cur_pos_product_len)
        return max_len

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        arrs=[[]]
        for i in nums:
            if i:
                arrs[-1].append(i)
            else:
                arrs.append([])
        ans=0
        for arr in arrs:
            if not len(arr):
                continue
            negs=0
            for i in arr:
                if i<0:
                    negs+=1
            if negs%2:
                p1=0
                while arr[p1]>0:
                    p1+=1
                p2=len(arr)-1
                while arr[p2]>0:
                    p2-=1
                ans=max(len(arr)-p1-1,p2,ans)
            else:
                ans=max(ans,len(arr))
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        pos_length = 0
        neg_length = 0
        max_length = 0
        for num in nums:
            if num > 0:
                pos_length += 1
                if neg_length:
                    neg_length += 1
            elif num < 0:
                tmp = pos_length
                if neg_length:
                    pos_length = neg_length + 1
                else:
                    pos_length = 0
                neg_length = tmp + 1
            else:
                pos_length = 0
                neg_length = 0
            max_length = max(max_length, pos_length)
#           print(f'num, max_length = {num}, {max_length}')
        max_length = max(max_length, pos_length)
        return max_length


class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[0, 0] for _ in range(n)]
        for i in range(n):
            if nums[i] == 0: dp[i] = [0, 0]
            elif i == 0 or nums[i - 1] == 0:
                if nums[i] > 0: dp[i][0] = 1
                else: dp[i][1] = 1
            elif nums[i] > 0:
                dp[i][0] = dp[i - 1][0] + 1
                if dp[i - 1][1] > 0: dp[i][1] = dp[i - 1][1] + 1
            else:
                if dp[i - 1][1] > 0: dp[i][0] = dp[i - 1][1] + 1
                dp[i][1] = dp[i - 1][0] + 1
        return max(dp[i][0] for i in range(n))

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        nums.append(0)
        left = 0
        n = len(nums)
        first_neg = n
        last_neg = 0
        ct_neg = 0
        ans = 0
        for right in range(n):
            if nums[right]<0:
                first_neg = min(first_neg, right)
                last_neg = max(last_neg, right)
                ct_neg += 1
            elif nums[right]==0:
                if left < right:
                    if ct_neg & 1 == 0:
                        ans = max(ans, right-left)
                    else:
                        print(left, right, first_neg, last_neg)
                        ans = max(ans, right-first_neg-1)
                        ans = max(ans, last_neg-left)
                left = right+1
                first_neg = n
                last_neg = 0
                ct_neg = 0
        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        res = 0
        for is_pos, group in itertools.groupby(nums, key = bool):
            if is_pos:
                subgroup = list(group)
                num_negs = 0
                # if the num negs is odd, the answer is either
                # the length without the first negative
                # or the length without the last negative
                first = last = None 
                for i, n in enumerate(subgroup):
                    if n < 0:
                        num_negs += 1
                        if first is None:
                            first = i
                        last = i
                if num_negs % 2 == 0:
                    res = max(res, len(subgroup))
                else:
                    res = max(res, first, len(subgroup) - 1 - first)
                    res = max(res, last, len(subgroup) - 1 - last)
        return res

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        neg = [0] * n
        pos = [0] * n 

        if nums[0] < 0:
            neg[0] = 1 
        elif nums[0] > 0:
            pos[0] = 1
        # 以i为结尾的时候 乘积是负数的时候的长度 neg[i], or is positive 
        for i in range(1, n):
            val = nums[i]
            if val > 0:
                pos[i] = pos[i-1] + 1
                neg[i] = (neg[i-1] + 1) if neg[i-1] != 0 else 0 
            elif val < 0:
                pos[i] = (neg[i-1] + 1) if neg[i-1] != 0 else 0
                neg[i] = pos[i-1] + 1
            else:
                pos[i] = 0
                neg[i] = 0
            print((pos[i], neg[i]))
        return max(pos)


class Solution:
    
    # space optimized
    def getMaxLen(self, nums: List[int]) -> int:
        
        ans = 0
        neg_pos = None
        neg_count = 0
        left = -1
        for i, n in enumerate(nums):
            if n==0:
                neg_pos = None
                neg_count = 0
                left = i
                continue
            elif n>0:
                if neg_count%2==0:
                    ans = max(ans, i-left)
                else:
                    ans = max(ans, i-neg_pos)
            elif n<0:
                neg_count += 1
                if neg_pos is None:
                    neg_pos=i
                if neg_count%2==0:
                    ans = max(ans, i-left)
                else:
                    ans = max(ans, i-neg_pos)

        return ans
    
    # original O(n) space
    def getMaxLen1(self, nums: List[int]) -> int:
        
        ans = 0
        dq = []
        left = -1
        for i, n in enumerate(nums):
            if n==0:
                dq.clear()
                left = i
                continue
            elif n>0:
                if len(dq)%2==0:
                    ans = max(ans, i-left)
                else:
                    ans = max(ans, i-dq[0])
            elif n<0:
                dq.append(i)
                if len(dq)%2==0:
                    ans = max(ans, i-left)
                else:
                    ans = max(ans, i-dq[0])

        return ans

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        f_pos = 0
        f_neg = 0
        max_pos = 0
        for i in range(len(nums)):
            if nums[i]==0:
                f_pos,f_neg = 0,0
            elif nums[i]>0:
                f_pos +=1
                if f_neg>0:
                    f_neg+=1
            else:
                tmp = f_pos
                if f_neg>0:
                    f_pos = f_neg+1
                else:
                    f_pos = 0
                f_neg = tmp+1
            print((i, f_pos,f_neg))
            max_pos = max(max_pos ,f_pos)
        return max_pos
            


from typing import List
class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        def aux(i,j):
            negs = 0
            for v in nums[i:j+1]:
                if v<0:
                    negs+=1
            if negs%2 == 0:
                return j-i+1
            l=i
            while nums[l]>0:
                l+=1
            l = j-l
            r=j
            while nums[r]>0:
                r-=1
            r = r-i
            return max(l,r)

        start = 0
        maxm = 0
        for end in range(len(nums)):
            if nums[end] == 0:
                maxm = max(maxm,aux(start, end-1))
                start = end+1
            elif nums[end]>0:
                maxm = max(maxm, 1)
        if start!=len(nums)-1:
            maxm = max(maxm,aux(start, len(nums)-1))
        return maxm



import bisect
class Solution:
    ans = [0 for i in range(100001)]
    def getMaxLen(self, nums: List[int]) -> int:
        def solve(arr):
            s1, s2 = set(), set()
            s1.add(-1)
            ret = 0
            cnt = 0
            n = len(arr)
            for i, c in enumerate(arr):
                cnt += 0 if c > 0 else 1
                if cnt % 2 == 0:
                    s1.add(i)
                else:
                    s2.add(i)
            if s1:
                ret = max(s1) - min(s1)
            if s2:
                ret = max(max(s2) - min(s2), ret)
            # print(s1, s2, ret)
            return ret
        ans = 0
        l = 0
        for i, c in enumerate(nums):
            if c == 0:
                ans = max(ans, solve(nums[l:i]))
                l = i + 1
        ans = max(ans, solve(nums[l:]))
        return ans