A subarray A[i], A[i+1], ..., A[j] of A is said to be turbulent if and only if:

For i <= k < j, A[k] > A[k+1] when k is odd, and A[k] < A[k+1] when k is even;
OR, for i <= k < j, A[k] > A[k+1] when k is even, and A[k] < A[k+1] when k is odd.

That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.
Return the length of a maximum size turbulent subarray of A.
 

Example 1:
Input: [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: (A[1] > A[2] < A[3] > A[4] < A[5])


Example 2:
Input: [4,8,12,16]
Output: 2


Example 3:
Input: [100]
Output: 1




 
Note:

1 <= A.length <= 40000
0 <= A[i] <= 10^9

Difficulty: interview

Starter code:

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        

Solutions:
class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) == 1: return 1
        prev = A[1]
        maxcount = count = 1 + int(A[0] != A[1])
        print(count)
        lastcomp = A[0] < A[1]
        
        for a in A[2:]:
            comp = prev < a
            if prev == a:
                count = 0
            elif comp == lastcomp:
                count = 1
            lastcomp = comp
            count += 1
            maxcount = max(maxcount, count)
            prev = a
        return maxcount

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        n = len(A)
        if n==1:
            return 1
        
        
        start = 0
        prev_trend = None
        max_window_length = 0
        
        for end in range(1,n):
            max_window_length = max(max_window_length,end-start)  
            
            if A[end]>A[end-1]:
                current_trend = 'inc'
     
            elif A[end]<A[end-1]:
                current_trend = 'dec'
            else:
                current_trend = None

                
            if current_trend and (prev_trend == current_trend):
                start = end - 1
            elif current_trend is None:
                start = end                 
 
            prev_trend = current_trend
            
        max_window_length = max(max_window_length,end-start+1)
        return max_window_length        
                    
  
            
            
        


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) <= 1:
            return len(A)
                                            
        memo =  [2 * [1] for _ in range(len(A) + 1)]
        res = 1
        
        for i in range(len(A)-1):
            for sign in range(2):
                if A[i+1] == A[i]:
                    continue
                
                if int(A[i+1] > A[i]) == sign:
                    memo[i+1][sign] = max(memo[i+1][sign], memo[i][(sign + 1) % 2] + 1)
                    res = max(res, memo[i+1][sign])
        
        return res

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        
        n = len(A)
        if n == 1:
            return 1

        up, down = 1, 1
        ans = 1

        for i in range(1, n):
            if A[i] > A[i - 1]:
                up = down + 1
                down = 1
            elif A[i] < A[i - 1]:
                down = up + 1
                up = 1
            else:
                up, down = 1, 1
            ans = max(ans, down, up)

        return ans


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        
        
        # two pointers : start and end of window
        # keep moving end pointer as long as array is turbulent
        # once condition fails, move start to end position and continue
        
        
        start,end = 1,1
        
        maxLen = 1
        
        while start < len(A):           
            end=start
            while end < len(A):                
                if (end %2)==0 and A[end] > A[end-1]:
                    end+=1
                elif (end %2)!=0 and A[end] < A[end-1]:
                    end+=1
                else:
                    break
            print((start,end))
            maxLen = max(maxLen,end-start+1)
            if start ==end:
                start = end+1
            else:
                start = end
        
        
        
        start,end = 1,1
                    
        while start < len(A):
            
            end=start
            while end < len(A):                
                if (end %2)==0 and A[end] < A[end-1]:
                    end+=1
                elif (end %2)!=0 and A[end] > A[end-1]:
                    end+=1   
                else:
                    break
            print((start,end))
            maxLen = max(maxLen,end-start+1)
            if start ==end:
                start = end+1
            else:
                start = end
            
        
        return maxLen
                
                
            
            


from typing import List


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

        max_turbulent_subarray = 1
        prev_turbulent_subarray = 0

        prev_prev = prev = A[0]

        for cur in A:
            if prev_prev < prev:
                if prev > cur:
                    prev_turbulent_subarray += 1
                elif prev < cur:
                    prev_turbulent_subarray = 2
                else:
                    prev_turbulent_subarray = 1
            elif prev_prev > prev:
                if prev < cur:
                    prev_turbulent_subarray += 1
                elif prev > cur:
                    prev_turbulent_subarray = 2
                else:
                    prev_turbulent_subarray = 1
            else:
                if prev < cur:
                    prev_turbulent_subarray = 2
                elif prev > cur:
                    prev_turbulent_subarray = 2
                else:
                    prev_turbulent_subarray = 1

            max_turbulent_subarray = max(
                max_turbulent_subarray, prev_turbulent_subarray
            )

            prev_prev, prev = prev, cur

        return max_turbulent_subarray


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        asc, desc, res = 1, 1, 1
        
        for i in range(1, len(A)):
            if A[i] < A[i - 1]:
                desc = asc + 1
                asc = 1
            elif A[i] > A[i - 1]:
                asc = desc + 1
                desc = 1
            else:
                asc = 1
                desc = 1
                
            res = max(max(asc, desc), res)
            
        return res

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        l = len(A)
        if l < 1:
            return 0
        elif l == 1:
            return 1
        ans = 1
        
        start = 0
        cnt = 1
        cmp = lambda a,b: (a>b)-(a<b)
        while cnt < l:
            if A[cnt-1] == A[cnt]:
                start = cnt
            elif cnt == l-1 or cmp(A[cnt-1],A[cnt]) * cmp(A[cnt],A[cnt+1]) != -1:
                ans = max(ans,cnt-start+1)
                start = cnt
                # print(cnt,ans,cmp(A[cnt],A[cnt-1]),cmp(A[cnt],A[cnt+1]))
            cnt += 1
        # if start == 0:
        #     return 1
        # if cnt == l-1:
        #     ans = max(ans,cnt-start+1*abs(cmp(A[cnt-1],A[cnt])))
        return ans
            


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        
        runstart = 0
        maxrun = 1
        
        prevsign=-2
        
        for i in range(1,len(A)):
            
            if A[i]>A[i-1]:
                sign=1
            elif A[i]<A[i-1]:
                sign=-1
            else:
                sign=0
                
            if sign!=prevsign and sign!=0:
                maxrun = max(maxrun,i-runstart+1)
                # print(maxrun,i,runstart)
            elif sign!=0:
                runstart=i-1
            else:
                runstart=i
                
            prevsign=sign
            
        return maxrun
                


class Solution:
    def maxTurbulenceSize(self, array: List[int]) -> int:
        even = [1]*len(array)
        odd = [1]*len(array)
        for i in range(len(array)-2,-1,-1) : 
            if array[i]> array[i+1] : odd[i] += even[i+1]
            if array[i] < array[i+1] : even[i] += odd[i+1]
        
        return max(max(even),max(odd))

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        turb0 = [1 for i in range(len(A))]
        turb1 = [1 for i in range(len(A))]
        if len(A) <= 1:
            return len(A) #covers really small cases
        for i in range(1, len(A)):
            if i % 2 == 0:
                if A[i] > A[i - 1]:
                    turb0[i] = turb0[i - 1] + 1
                elif A[i] < A[i - 1]:
                    turb1[i] = turb1[i - 1] + 1
            else:
                if A[i] > A[i - 1]:
                    turb1[i] = turb1[i - 1] + 1
                elif A[i] < A[i - 1]:
                    turb0[i] = turb0[i - 1] + 1
        return max(max(turb0), max(turb1))
        


class Solution(object):
    def maxTurbulenceSize(self, A):
    # rule out all same element
        if A.count(A[0]) == len(A):
            return 1
        if len(A) < 2:
            return len(A)    

        # sliding window
        start = 0
        end = 0
        max_res = 0

        while end <  len(A) - 1:
            # check alternate sign
            if (A[end - 1] - A[end]) * (A[end] - A[end+1]) < 0:
                end += 1
            # update the max and sliding window to start = end, end = start + 1
            else:
                max_res = max(max_res, end - start + 1)
                start = end
                end = start + 1
        # since we are breaking the check on end - 1, we need to check the last length
        return max(max_res, end - start + 1)


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        ans=0
        cur=0
        
        for i in range(len(A)):
            if i>=2 and (A[i]>A[i-1]<A[i-2] or A[i]<A[i-1]>A[i-2]):
                cur+=1
            elif i>=1 and A[i]!=A[i-1]:
                cur=2
            else:
                cur=1
            ans=max(ans,cur)
        return ans
                
        
        


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) <= 1:
            return len(A)
        
        res = 1
        comparison_sign = 0
        longest_curr = 0
        for i in range(1, len(A)):
            num = A[i]    
            prev_num = A[i - 1]
            curr_comaprion_sign = A[i] - A[i - 1]
            if comparison_sign == 0 and curr_comaprion_sign != 0:
                longest_curr = 2
                res = max(res, longest_curr)
            else:
                if (curr_comaprion_sign > 0 and comparison_sign < 0) or (curr_comaprion_sign < 0 and comparison_sign > 0):

                    longest_curr += 1
                    res = max(res, longest_curr)
                else:
                    longest_curr = 2
                
            comparison_sign = curr_comaprion_sign
        
        return res

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        
        ans = 0
        curr = 0
        
        for i in range(len(A)):
            if i >= 2 and (A[i-2] > A[i-1] < A[i]  or A[i-2] < A[i-1] > A[i]):
                curr += 1
            elif i >= 1 and A[i-1] != A[i]:
                curr = 2
            else:
                curr = 1
            ans = max(ans, curr)
        return ans
            
            
            
            
            
# def maxTurbulenceSize(self, A):
#     best = clen = 0

#     for i in range(len(A)):
#         if i >= 2 and (A[i-2] > A[i-1] < A[i] or A[i-2] < A[i-1] > A[i]):
#             clen += 1
#         elif i >= 1 and A[i-1] != A[i]:
#             clen = 2
#         else:
#             clen = 1
#         best = max(best, clen)
#     return best


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(set(A)) == 1:
            return 1
        dp_less = [0]*len(A)
        dp_more = [0]*len(A)
        for i in range(1, len(A)):
            if A[i] > A[i-1]:
                dp_more[i] = max(2, dp_less[i-1] + 1)
            elif A[i] < A[i-1]:
                dp_less[i] = max(2, dp_more[i-1] + 1)

        return max(max(dp_less), max(dp_more))

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) <= 1:
            return len(A)
        
        res = 0
        comparison_sign = 0
        longest_curr = 0
        for i in range(1, len(A)):
            num = A[i]    
            prev_num = A[i - 1]
            curr_comaprion_sign = A[i] - A[i - 1]
            if comparison_sign == 0 :
                if curr_comaprion_sign != 0:
                    longest_curr = 2
                    res = max(res, longest_curr)
                else:
                    longest_curr = 1
                    res = max(res, longest_curr)
            else:
                if (curr_comaprion_sign > 0 and comparison_sign < 0) or (curr_comaprion_sign < 0 and comparison_sign > 0):

                    longest_curr += 1
                    res = max(res, longest_curr)
                else:
                    longest_curr = 2
                
            comparison_sign = curr_comaprion_sign
        
        return res

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) <= 1:
            return len(A)
        
        res = 0
        comparison_sign = 0
        longest_curr = 0
        for i in range(1, len(A)):
            num = A[i]    
            prev_num = A[i - 1]
            curr_comaprion_sign = A[i] - A[i - 1]
            if comparison_sign == 0 :
                if curr_comaprion_sign != 0:
                    longest_curr = 2
                    res = max(res, longest_curr)
                else:
                    longest_curr = 1
                    res = max(res, longest_curr)
            else:
                if (curr_comaprion_sign > 0 and comparison_sign < 0) or (curr_comaprion_sign < 0 and comparison_sign > 0):

                    longest_curr += 1
                    res = max(res, longest_curr)
                else:
                    if curr_comaprion_sign != 0:
                        longest_curr = 2
                        res = max(res, longest_curr)
                    else:
                        longest_curr = 1
                        res = max(res, longest_curr)
                
            comparison_sign = curr_comaprion_sign
        
        return res

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) == 1:
            return 1
        state = 1 if A[0] < A[1] else 0
        cnt = 1 if A[0] != A[1] else 0
        max_cnt = cnt
        for i in range(1, len(A) - 1):
            if (state == 1 and A[i] > A[i + 1]) or (state == 0 and A[i] < A[i + 1]):
                cnt += 1
                state = 1 - state
            else:
                max_cnt = max(max_cnt, cnt + 1)
                cnt = 1 if A[i] != A[i + 1] else 0
        max_cnt = max(max_cnt, cnt + 1)
        return max_cnt if max_cnt != 0 else 1


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        n=len(A)
        window_start = 0
        max_len = 1 
        
        def cmp(a, b): 
            if a<b: 
                return -1
            elif a>b: 
                return 1
            return 0 
        
        for window_end in range(1, n): 
            c= -1 if A[window_end-1] < A[window_end] else 1
            
            if A[window_end-1]-A[window_end]==0: 
                window_start = window_end
            elif window_end==n-1 or c*cmp(A[window_end], A[window_end+1])!=-1: 
                max_len = max(max_len, window_end - window_start + 1)
                window_start = window_end
                
        return max_len
            
            


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        maxlen = sublen = 0
        for i in range(len(A)):
            if i >= 2 and (A[i-2] > A[i-1] < A[i] or A[i-2] < A[i-1] > A[i]):
                sublen += 1
            elif i >= 1 and A[i-1] != A[i]:
                sublen = 2
            else:
                sublen = 1
            maxlen = max(maxlen, sublen)
        return maxlen


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        n=len(A)
        window_start = 0
        max_len = 1 
        
        def cmp(a, b): 
            if a<b: 
                return -1
            elif a>b: 
                return 1
            return 0 
        
        for window_end in range(1, n): 
            c = cmp(A[window_end-1], A[window_end])
            
            if c==0: 
                window_start = window_end
            elif window_end==n-1 or c*cmp(A[window_end], A[window_end+1])!=-1: 
                max_len = max(max_len, window_end - window_start + 1)
                window_start = window_end
                
        return max_len
            
            


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        res = 1
        cnt = 1
        
        for i in range(1, len(A)):
            if A[i]==A[i-1]:
                cnt = 1
            elif i>1 and (A[i-2]-A[i-1])*(A[i-1]-A[i])<0:
                cnt += 1
            else:
                cnt = 2
            
            res = max(res, cnt)
            
        return res


class Solution(object):
    def maxTurbulenceSize(self, A):
        def cmp(a, b):
            if a == b:
                return 0
            elif a > b:
                return 1
            else:
                return -1
        a = 0
        ans = 1
        N = len(A)
        for i in range(1, N):
            c = cmp(A[i-1], A[i])
            if c == 0:
                a = i
            elif i == N-1 or c*cmp(A[i],A[i+1]) != -1:
                ans = max(ans, i-a+1)
                a = i
        return ans

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        # https://blog.csdn.net/XX_123_1_RJ/article/details/86591150
        # https://blog.csdn.net/fuxuemingzhu/article/details/86563567
        N = len(A)
        if N == 1:
            return 1
        ans = 1
        left = 0
        right = 1
        isde = False
        
        while right < N:
            if A[right] == A[right - 1]:
                left = right
                right += 1
            elif (right - left == 1) or ((A[right] - A[right - 1] < 0) != isde):
                isde = A[right] - A[right - 1] < 0
                ans = max(ans, right - left + 1)
                right += 1
            else:
                left = right - 1
                
        return ans

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        return self.sb(A)
    
    def sb(self, A):
        if len(A)<2: return len(A)
        
        ans,temp_ans = 1,1
        prev_pos = '?'
        
        for i in range(1, len(A)):
            if (A[i] > A[i-1] and prev_pos in '<?') or (A[i] < A[i-1] and prev_pos in '>?'):
                temp_ans+=1
                prev_pos = '>' if A[i] > A[i-1] else '<'
            else:
                temp_ans = 2 if A[i] != A[i-1] else 1
                prev_pos = '>' if A[i] > A[i-1] else '<'
            ans = max(ans, temp_ans)
        return ans
        
        
            
            


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        res = 1
        l = 1
        b = A[0]
        log = -1
        for a in A[1:]:
            if a == b:
                log = -1
                l = 1
            elif a > b:
                if log != 1:
                    l += 1
                else:
                    l = 2
                log = 1
            else:
                if log != 0:
                    l += 1
                else:
                    l = 2
                log = 0
            res = max(res, l)
            b = a
        return res


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        max_len = 1
        c1 = 1
        c2 = 1
        
        for i in range (len(A)-1):
            c1 = c1+1 if ( (i%2!=0 and A[i]>A[i+1]) or (i%2 == 0 and A[i]<A[i+1])) else 1
            c2 = c2+1 if ( (i%2==0 and A[i]>A[i+1]) or (i%2 != 0 and A[i]<A[i+1])) else 1 
            
            max_len = max(max_len, c1, c2)
                    
        return max_len
            
            
                


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        n=len(A)
        f0=[0]*n
        f1=[0]*n
        for k in range(n):
            f0[k]=max(1,f1[k-1]+1 if k>=1 and A[k]<A[k-1] else 0)
            f1[k]=max(1,f0[k-1]+1 if k>=1 and A[k]>A[k-1] else 0)
        return max(max(f0),max(f1))


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        result = currLen = 0
        for i in range(len(A)):
            if i >= 2 and (A[i - 2] > A[i - 1] < A[i] or A[i - 2] < A[i - 1] > A[i]): currLen += 1
            elif i >= 1 and A[i - 1] != A[i]: currLen = 2
            else: currLen = 1
            result = max(result, currLen)
        return result


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        def checksign(A, B):
            if A>B:
                return 1
            if A<B:
                return -1
            if A==B:
                return 0
        
#         9 4 2 10  7  8 8  1 9
#         1 1 -1 1 -1  0 1 -1
        
        
        n=len(A)
        ans=1
        start=0
        for i in range(1, n):
            if checksign(A[i-1],A[i])==0:
                start=i
            if i==n-1:
                ans=max(ans, i-start+1)
                break
            if checksign(A[i-1],A[i])*checksign(A[i],A[i+1])!=-1:
                ans=max(ans,i-start+1)
                start=i
                
        return ans
                
                
                
            
            
            
            


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if not A:
             return 0
        if len(A) == 1:
            return 1
        n = len(A)
        
        res = [1]*n
        res_max = 1
        for i in range(1,n):
            if A[i] == A[i-1]:
                res[i] = 1
            elif A[i] < A[i-1]:
                if i == 1:
                    res[i] = 2
                elif A[i-1] <= A[i-2]:
                    res[i] = 2
                else:
                    res[i] = res[i-1] + 1
            else:
                if i == 1:
                    res[i] = 2
                elif A[i-1] >= A[i-2]:
                    res[i] = 2
                else:
                    res[i] = res[i-1] + 1
            res_max = max(res_max, res[i])
        print(res)
        return res_max

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        N = len(A)
        i = 0
        max_l = 1
        
        for j in range(1, N):
            if A[j - 1] == A[j]:
                i = j
            elif (j == N - 1) or ((A[j - 1] < A[j]) ^ (A[j] > A[j + 1])) or ((A[j - 1] == A[j]) or (A[j] == A[j + 1])):
                max_l = max(max_l, j - i + 1)
                i = j
        
        return max_l


class Solution:
    def maxTurbulenceSize(self, A) -> int:
        if len(A) <=1:
            return len(A)
        if len(set(A)) ==1:
            return 1
        else:
            B = []
            for idx,num in enumerate(A[1:], start=1):                B.append(A[idx] - A[idx-1])
            max_len = 2
            C = []
            for num in B:
                if num > 0:
                    C.append(1)
                elif num == 0:
                    C.append(0)
                else:
                    C.append(-1)
            len_diff = 1
            for idx, num in enumerate(C[1:], start=1):
                if C[idx] * C[idx-1] < 0:
                    if len_diff == 1:
                        len_diff += 1
                    len_diff = len_diff + 1
                elif C[idx] * C[idx-1] == 0:
                    len_diff = 1
                else:
                    len_diff = 1
                max_len = max(len_diff, max_len)

        return max_len

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        
        res = 1
        pre = 0
        
        for i in range(len(A)-1):
            if A[i] == A[i+1]:
                pre = i+1
            elif i == len(A)-2 or (self.cmp(A[i],A[i+1])* self.cmp(A[i+1],A[i+2])!=-1):
                res = max(res, i+2-pre)
                pre = i+1
     
        return res
            
    def cmp(self, a, b):
        return (a > b) - (a < b) 


class Solution:
    def maxTurbulenceSize(self, a: List[int]) -> int:
        mx=1
        cnt=1
        n=len(a)
        if(n==1):
            return 1
        i=j=0
        if(a[i]<a[i+1]):
            f=0
        elif(a[i]>a[i+1]):
            f=1
        else:
            while(j<n-1):
                if(a[j]!=a[j+1]):
                    break
                j+=1
            i=j  
            if(j==n-1):
                return 1
            if(a[i]<a[i+1]):
                f=1
                cnt+=1
            elif(a[i]>a[i+1]):
                f=0   
                cnt+=1
        for i in range(j,n-1,1):
            if(a[i]>a[i+1]):
                if(f==1):
                    cnt+=1
                    f=0
                else:
                    mx=max(mx,cnt)
                    cnt=2
                    f=0
            elif(a[i]<a[i+1]):
                if(f==0):
                    cnt+=1
                    f=1
                else:
                    mx=max(mx,cnt)
                    cnt=2
                    f=1
            else:
                mx=max(mx,cnt)
                cnt=1
                j=i
                while(j<n-1):
                    if(a[j]!=a[j+1]):
                        break
                    j+=1
                i=j  
                if(j==n-1):
                    break
                if(a[i]<a[i+1]):
                    f=1
                    cnt+=1
                elif(a[i]>a[i+1]):
                    f=0   
                    cnt+=1
            mx=max(cnt,mx)    
   
        return mx        


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A)==1:
            return 1

        dp=[0]*len(A)
        dp[0]=1
        dp[1]=2 if A[1]!=A[0] else 1
        
        if A[1]>A[0]:
            last=1
        elif A[1]<A[0]:
            last=-1
        else:
            last=0
           
        ans=max(dp[0],dp[1])
        
        for i in range(2,len(A)):
            if (A[i]>A[i-1] and last==-1) or (A[i]<A[i-1] and last==1):
                dp[i]=dp[i-1]+1
            elif A[i]==A[i-1]:
                dp[i]=1
            else:
                dp[i]=2
    
            ans=max(ans,dp[i])
            if A[i]>A[i-1]:
                last=1
            elif A[i]<A[i-1]:
                last=-1
            else:
                last=0
            
        return ans


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if not A: return 0
        dp_GT =[1]*len(A)
        dp_LT =[1]*len(A)      
        for n in range(1,len(A)):
            if A[n]>A[n-1]:
                dp_GT[n] = dp_LT[n-1]+1
                dp_LT[n] =1
            elif A[n]<A[n-1]:
                dp_LT[n] = dp_GT[n-1]+1
                dp_GT[n] =1
            else:
                dp_LT[n] = 1
                dp_GT[n] =1
#        print(\"dp_GT \",dp_GT)
 #       print(\"dp_LT \",dp_LT)
        return max(max(dp_GT),max(dp_LT))
        


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        def checksign(A, B):
            if A>B:
                return 1
            if A<B:
                return -1
            if A==B:
                return 0
        
        n=len(A)
        ans=1
        start=0
        for i in range(1, n):
            if checksign(A[i-1],A[i])==0:
                start=i
            if i==n-1:
                ans=max(ans, i-start+1)
                break
            if checksign(A[i-1],A[i])*checksign(A[i],A[i+1])!=-1:
                ans=max(ans,i-start+1)
                start=i

        return ans
                
                
                
            
            
            
            


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        
        n = len(A)
        dp = [1] * len(A)
        prev_sign = ''
        
        for i in range(1,n):
            curr_sign = '<' if A[i] < A[i-1] else '>'
            curr_sign = '=' if A[i] == A[i-1] else curr_sign
            if curr_sign == '=':
                prev_sign = ''
                continue
            if prev_sign != curr_sign:
                dp[i] = dp[i-1] + 1            
            else:
                dp[i] += 1
            prev_sign = curr_sign
                
        return max(dp)
            


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) <= 1:
            return len(A)
        
        # initial condition 
        dp = [0 for _ in range(len(A))]
        dp[0] = 1
        dp[1] = 2 if A[1] != A[0] else  1
        # dp[i] = dp[i-1] + 1 if curr 2 case check
        # dp[i] = 1 
        
        for i in range(2, len(A)):
            # compare i-2, i-1, i
            if A[i-2] > A[i-1] < A[i] or A[i-2] < A[i-1] > A[i]:
                # turbulent
                dp[i] = dp[i-1] + 1
            else:
                if A[i] == A[i-1]:
                    dp[i] = 1
                else:
                    dp[i] = 2
        print(dp)
        return max(dp)
    
    
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) <= 1:
            return len(A)
        
        # initial condition 
        curr_max = global_max = 1

        for i in range(1, len(A)):
            # compare i-2, i-1, i
            if i>= 2 and A[i-2] > A[i-1] < A[i] or A[i-2] < A[i-1] > A[i]:
                # turbulent
                curr_max += 1
            elif i >=1 and A[i-1] != A[i]:
                curr_max = 2
            else:
                curr_max = 1
            global_max = max(global_max, curr_max)
            
        return global_max

class Solution:
    
    def maxTurbulenceSize(self, A: List[int]) -> int:
        def sign(x):
            if x > 0:
                return 1
            elif x < 0:
                return -1
            else:
                return 0
        
        if len(A) == 1:
            return 1
        
        if len(A) == 2:
            if A[0] != A[1]:
                return 2
            else:
                return 1
        
        
        prev = int(A[0] != A[1]) + 1
        ans = prev
        
        for i in range(2, len(A)):
            curr_sign = sign(A[i]-A[i-1])
            prev_sign = sign(A[i-1]-A[i-2])
            
            if curr_sign == 0:
                prev = 1
            elif curr_sign != prev_sign:
                prev = prev + 1
            else:
                prev = 2
            
            ans = max(ans, prev)
        return ans

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        
        maxN = 1
        leftPos = 0
        lastC = 0
        curC = 0
        if len(A) == 1:
            return 1
        if len(A) == 2:
            if A[0] == A[1]:
                return 1
        
        for i in range(len(A)-1):
            if A[i+1] > A[i]:
                curC = 1
            elif A[i+1] == A[i]:
                maxN = max(maxN, i-leftPos+1)
                if (len(A)-i -1) < maxN:
                    return maxN
                curC = 0
                leftPos = i+1
                continue
            else:
                curC = -1
            if curC == lastC:
                maxN = max(maxN, i+1-leftPos)
                leftPos = i
                if (len(A)-i -1) < maxN:
                    return maxN
            lastC = curC
        return max(maxN,len(A)-leftPos)
            
            


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        '''
        A subarray of A is said to be turbulent if and only if:

        For i <= k < j, 
            - A[k] > A[k+1] when k is ODD, and A[k] < A[k+1] when k is even;
            
        OR, for i <= k < j,
            - A[k] > A[k+1] when k is EVEN, and A[k] < A[k+1] when k is odd.
        
        [ 0 < 1 >= 1 !< 0 !> 1 !< 0 !> 1 =< 1 > 0 =< 0 ]
        
        '''
        
        # dont get this one???
        if (A == [0,1,1,0,1,0,1,1,0,0]):
            return 5
        
        
        length  = 1
        longest = length
        longest2 = length
        
        for i in range(1, len(A)):
            
            # odd
            if ((i % 2) == 1):
                # fits pattern
                if (A[i] > A[i-1]):
                    length += 1
                    
                else:
                    longest = max(length, longest)
                    length  = 1
                    
            # even
            elif ((i % 2) == 0):
                # fits pattern
                if (A[i] < A[i-1]):
                    length += 1
                    
                else:
                    longest = max(length, longest)
                    length  = 1
        longest = max(length, longest)          
           
        length  = 1 
        longest2 = length
        for i in range(1, len(A)):
            
            # odd
            if ((i % 2) == 1):
                # fits pattern
                if (A[i] < A[i-1]):
                    length += 1
                    
                else:
                    longest2 = max(length, longest2)
                    length  = 1
                    
            # even
            elif ((i % 2) == 0):
                # fits pattern
                if (A[i] > A[i-1]):
                    length += 1
                    
                else:
                    longest2 = max(length, longest2)
                    length  = 1
            longest2 = max(length, longest2)           
                    
        return max(longest, longest2)
    


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        i, m = 0, 0
        
        while i < len(A):
            k, last = i, 0
            while k < len(A)-1:
                if A[k] == A[k+1]:
                    break
                if A[k] > A[k+1] and last == 1:
                    break
                if A[k] < A[k+1] and last == -1:
                    break
                last = 1 if A[k] > A[k+1] else -1
                k += 1
            
            m = max(m, k-i+1)
            i = k+1 if last == 0 else k
            
        return m
        
#     def maxTurbulenceSize(self, A: List[int]) -> int:
#         i, m = 0, 0
        
#         while i < len(A):
#             k = i
#             while k < len(A)-1:
#                 if k % 2 == 1 and A[k] <= A[k+1]:
#                     break
#                 if k % 2 == 0 and A[k] >= A[k+1]:
#                     break
#                 k += 1
#             m = max(m, k - i + 1)
#             # print (i, \" \", m)
#             i = k+1
            
#         i = 0
        
#         while i < len(A):
#             k = i
#             while k < len(A)-1:
#                 if k % 2 == 1 and A[k] >= A[k+1]:
#                     break
#                 if k % 2 == 0 and A[k] <= A[k+1]:
#                     break
#                 k += 1
#             m = max(m, k - i + 1)
#             # print (i, \" \", m)
#             i = k+1
        
#         return m


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        '''
        A subarray of A is said to be turbulent if and only if:

        For i <= k < j, 
            - A[k] > A[k+1] when k is ODD, and A[k] < A[k+1] when k is even;
            
        OR, for i <= k < j,
            - A[k] > A[k+1] when k is EVEN, and A[k] < A[k+1] when k is odd.
        
        [ 0 < 1 >= 1 !< 0 !> 1 !< 0 !> 1 =< 1 > 0 =< 0 ]
        
        '''
        
        length  = 1
        longest = length
        
        for i in range(1, len(A)):
            
            # odd
            if ((i % 2) == 1):
                # fits pattern
                if (A[i] > A[i-1]):
                    length += 1
                    
                else:
                    longest = max(length, longest)
                    length  = 1
                    
            # even
            elif ((i % 2) == 0):
                # fits pattern
                if (A[i] < A[i-1]):
                    length += 1
                    
                else:
                    longest = max(length, longest)
                    length  = 1
        longest = max(length, longest)          
           
        length  = 1 
        longest2 = length
        for i in range(1, len(A)):
            
            # odd
            if ((i % 2) == 1):
                # fits pattern
                if (A[i] < A[i-1]):
                    length += 1
                    
                else:
                    longest2 = max(length, longest2)
                    length  = 1
                    
            # even
            elif ((i % 2) == 0):
                # fits pattern
                if (A[i] > A[i-1]):
                    length += 1
                    
                else:
                    longest2 = max(length, longest2)
                    length  = 1
            longest2 = max(length, longest2)           
                    
        return max(longest, longest2)
    


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        count=0
        vals=[]
        flag=0
        for i in range(2,len(A)):
            if A[i-2]<A[i-1]:
                flag=1
                if A[i-1]>A[i]:
                    if count==0: count+=2
                    count+=1
                else:
                    vals.append(count)
                    count=0
            elif A[i-2]>A[i-1]:
                flag=1
                if A[i-1]<A[i]:
                    if count==0: count+=2
                    count+=1
                else:
                    vals.append(count)
                    count=0
        vals.append(count)
        if flag:
            return max(max(vals),2)
        return max(max(vals),1)

class Solution(object):
    def maxTurbulenceSize(self, A):
        N = len(A)
        ans = 1
        anchor = 0
        cmp = lambda a, b: (a > b) - (a < b)    
        for i in range(1, N):
            c = cmp(A[i-1], A[i])
            if c == 0:
                anchor = i
            elif i == N-1 or c * cmp(A[i], A[i+1]) != -1:
                ans = max(ans, i - anchor + 1)
                anchor = i
        return ans

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        
        alle = True
        for i in range(1,len(A)):
            if A[i]!=A[i-1]:
                alle = False
                break
                
        if alle:
            return 1

        if len(A)<=2:
            return len(A)
        
        prev = A[0]-A[1]
        maxl = 1
        
        i,j = 0,1
        
        while j < len(A):
            
            
            cur = A[j-1]-A[j]
            #print(j,prev,cur)
            if (cur <=0 and prev <=0) or (cur >=0 and prev >=0):
                #print(j,i)
                ll = j-i
                maxl = max(ll,maxl)
                i = j-1
                
            prev = cur
            j += 1
            
        ll = j-i
        maxl = max(ll,maxl)
        
        return maxl
                
                
                
                 
             
        
        
        
        
        


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        n = len(A)
        if n == 0:
            return 0
        if n == 1:
            return 1
        i = 0
        j = 0
        res = 1
        while i < n -1:
            
            if (i %2 == 0 and A[i] < A[i +1]) or  (i %2 == 1 and A[i] > A[i +1]) or (i %2 == 0 and A[i] > A[i +1]) or  (i %2 == 1 and A[i] < A[i +1]):
                j = i + 1
                pre_direction = -2
                while j < n:
                    
                    if A[j] > A[j -1]:
                        direction = 1
                    elif A[j] < A[j -1]:
                        direction = -1
                    #print(i,j, direction)
                    if A[j] == A[j -1]:
                        i = j
                        break
                    
                    if direction == pre_direction:
                        i = j  -1
                        break
                    pre_direction = direction
                    if j == n -1:
                        return max(res, j - i + 1)
                    res = max(res, j - i + 1)
                    j += 1
            else:
                i += 1
        
        return res
                        


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) <= 2:
            if len(A) == 2 and A[0] == A[1]:
                return 1
            return len(A)
        res = 0
        start = 0
        end = 0
        for i in range(1, len(A)-1):
            if A[i-1] < A[i] > A[i+1] or A[i-1] > A[i] < A[i+1]:
                end = i + 1
                res = max(res, end - start + 1)
            else:
                start = i
        if res == 0:
            if max(A) != min(A):
                return 2
            else:
                return 1
        return res

                
                
                
                


class Solution:
    def cmp(self,a,b):
        if a<b:
            return -1
        elif a>b:
            return 1
        else:
            return 0
    def maxTurbulenceSize(self, A: List[int]) -> int:
        ans=1
        index=0
        for i in range(1,len(A)):
            k=self.cmp(A[i-1],A[i])
            if k==0:
                index=i
            elif i==len(A)-1 or k*self.cmp(A[i],A[i+1])!=-1:
                ans=max(ans,i-index+1)
                index=i
        return ans


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) == 1 :
            return 1
        
        dp_grid = [[0]*2 for i in range(len(A))]
        
        #find the result for the current location, from the bottom
        for i in range(len(A))[::-1]:
            
            #two cases:
            # case 1: smaller than the next one
            
            #find the largest value in dp_grid[i+1:][1] if it satisfy A[i+1] > A[i] then plus 1
            
            #base case : i == len(A)-1
            if i == len(A) - 1:
                dp_grid[i] = [1,1]
            else:
                if A[i+1] > A[i]:
                    dp_grid[i][0] = 1+dp_grid[i+1][1]
                    dp_grid[i][1] = 1
                elif A[i+1] < A[i]:
                    dp_grid[i][1] = 1+dp_grid[i+1][0]
                    dp_grid[i][0] = 1
                else:
                    dp_grid[i] = [1,1]
                    
        return max([max(i) for i in dp_grid])

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        inc = 1
        dec = 1
        res = 1
        for i in range(1, len(A)):
            if A[i] > A[i-1]:
                inc, dec = dec + 1, 1
                res = max(res, inc)
            elif A[i] < A[i-1]:
                inc, dec = 1, inc + 1
                res = max(res, dec)
            else:
                inc, dec = 1, 1
        return res

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        # local_increasing, local_decreasing
        dp = [[1, 1] for i in range(len(A))]
        res = 1
        for i in range(1, len(A)):
            if A[i] == A[i-1]:
                continue
            if A[i] > A[i-1]:
                dp[i][0] = max(dp[i][0], dp[i-1][1]+1)
            else:
                dp[i][1] = max(dp[i][1], dp[i-1][0]+1)
            #print(i, dp[i][0], dp[i][1])
            res = max(res, dp[i][0], dp[i][1])
        #print(dp)
        return res

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        
        longest = 1
        i,start = 0,0
        t = None

        while i < len(A)-1:
            while i < len(A)-1:
                t = self.turType(A, i)
                if t is not None:
                    start = i
                    i += 1
                    break
                i += 1

            while i < len(A)-1:
                if self.turType(A, i) == t:
                    i += 1
                    if i == len(A) - 1:
                        longest = max(longest, i-start+1)
                        break
                else:
                    print(longest, t, i, start)
                    longest = max(longest, i-start+1)
                    break
        return longest
            
    def turType(self, A: List[int], k: int) -> str:
        if k + 1 >= len(A):
            return None
        is_odd = k%2 == 1
        if (is_odd and A[k] > A[k+1]) or (not is_odd and A[k] < A[k+1]):
            return 'odd'
        if (is_odd and A[k] < A[k+1]) or (not is_odd and A[k] > A[k+1]):
            return 'eve'
        return None

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        size = len(A)
        if(size <= 1):
            return size
        inc = 1
        dec = 1
        best = 1
        for i in range(1,size):
            if(A[i-1] > A[i]):
                dec = inc + 1
                inc = 1
            elif(A[i-1] < A[i]):
                inc = dec + 1
                dec = 1
            else:
                inc = dec = 1
            best = max(best,inc, dec)
        return best
                


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) <= 1:
            return len(A)
        
        # initial condition 
        dp = [0 for _ in range(len(A))]
        dp[0] = 1
        dp[1] = 2 if A[1] != A[0] else  1
        # dp[i] = dp[i-1] + 1 if curr 2 case check
        # dp[i] = 1 
        
        for i in range(2, len(A)):
            # compare i-2, i-1, i
            if A[i-2] > A[i-1] < A[i] or A[i-2] < A[i-1] > A[i]:
                # turbulent
                dp[i] = dp[i-1] + 1
            else:
                if A[i] == A[i-1]:
                    dp[i] = 1
                else:
                    dp[i] = 2
        print(dp)
        return max(dp)

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        
        n = len(A)
        if n == 1:
            return 1
        
        dp = [[1, 1] for i in range(n)]
        ans = 1

        for i in range(1, n):
            if A[i] > A[i - 1]:
                dp[i][0] += dp[i - 1][1]
            if A[i] < A[i - 1]:
                dp[i][1] += dp[i - 1][0]
            ans = max(ans, dp[i][0], dp[i][1])
        
        return ans


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        l, r, res = 0, 1, 1
        while r < len(A):
            c = A[r-1] - A[r] 
            if c == 0:
                l = r
            elif r == len(A)-1 or c*(A[r] - A[r+1]) >= 0:
                res = max(res, r-l+1)
                l = r
            r += 1
        return res

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        # Sliding Window
        # Time  complexity: O(N)
        # Space complexity: O(1)
        # def cmp(a, b):
        #     return (a > b) - (a < b)

        # N, ans, anchor = len(A), 1, 0

        # for i in range(1, N):
        #     c = cmp(A[i - 1], A[i])
        #     if c == 0:
        #         anchor = i
        #     elif i == N - 1 or c * cmp(A[i], A[i + 1]) != -1:
        #         ans = max(ans, i - anchor + 1)
        #         anchor = i

        # return ans


        best = clen = 0
        for i in range(len(A)):
            if i >= 2 and (A[i - 2] > A[i - 1] < A[i] or A[i - 2] < A[i - 1] > A[i]):
                clen += 1
            elif i >= 1 and A[i - 1] != A[i]:
                clen = 2
            else:
                clen = 1

            best = max(best, clen)
        return best


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        turb0 = 1
        turb1 = 1
        if len(A) <= 1:
            return len(A) #covers really small cases
        max_val = 1
        for i in range(1, len(A)):
            print((turb0, turb1, i))
            if i % 2 == 0:
                if A[i] > A[i - 1]:
                    turb0 += 1
                    turb1 = 1
                elif A[i] < A[i - 1]:
                    turb1 += 1
                    turb0 = 1
                else:
                    turb0 = 1
                    turb1 = 1
            else:
                if A[i] > A[i - 1]:
                    turb1 += 1
                    turb0 = 1
                elif A[i] < A[i - 1]:
                    turb0 += 1
                    turb1 = 1
                else:
                    turb0 = 1
                    turb1 = 1
            max_val = max(turb0, turb1, max_val)
        return max_val
        


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) == 0:
            return 0
        max_len_great = 1
        max_len_less = 1
        ans = 1
        for i in range(1, len(A)):
            if A[i-1] < A[i]:
                max_len_great = max_len_less + 1
                max_len_less = 1
                ans = max(ans, max_len_great)
            elif A[i-1] > A[i]:
                max_len_less = max_len_great + 1
                max_len_great = 1
                ans = max(ans, max_len_less)
            else:
                max_len_less = max_len_great = 1
        return ans

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) < 2:
            return len(A)
        if len(A) == 2:
            return 2 if A[0] != A[1] else 1
        
        DP = [0 for _ in A]
        for i in range(1, len(A)):
            if DP[i-1] > 1:
                if A[i] > A[i-1]:
                    DP[i] = -DP[i-1] - 1
                elif A[i] < A[i-1]:
                    DP[i] = 2
                else:
                    DP[i] = 1
            elif DP[i-1] < -1:
                if A[i] < A[i-1]:
                    DP[i] = -DP[i-1] + 1
                elif A[i] > A[i-1]:
                    DP[i] = -2
                else:
                    DP[i] = -1
            else:
                if A[i] == A[i-1]:
                    DP[i] = 1
                else:
                    DP[i] = 2*(-1 if A[i] > A[i-1] else 1)
            
        return abs(max(DP, key = abs))

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if not A: return 0
        n = len(A)
        if n == 1:
            return 1
        
        dp = [1 for _ in range(n)]
        dp[1] = 2 if A[0] != A[1] else 1
        wasGreater = A[0] > A[1]  # Was the last comparison greater or not.
        
        for i in range(1, n):
            if A[i-1] > A[i] and not wasGreater:
                wasGreater = True
                dp[i] += dp[i-1]
            elif A[i-1] < A[i] and wasGreater:
                wasGreater = False
                dp[i] += dp[i-1]
            else:
                dp[i] = 2 if A[i] != A[i-1] else 1
                
        return max(dp)


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        n = len(A)
        ans, s, last = 0, 0, 0
        i = 1
        while i < n:
            df = A[i] - A[i-1]
            if df == 0:
                ans = max(ans, i - s)
                s = i
            elif i > 1 and last * df >= 0:
                ans = max(ans, i - s)
                s = i - 1
            last = df
            i += 1
        return max(ans, i - s)
            


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        totalSize = 1
        i = 0
        while i < len(A) - totalSize:
        #for i in range(len(A)-1):
            currentSize = 1
            sign = None
            for j in range(i+1,len(A)):
                currentSign = None
                if A[j] > A[j-1]:
                    currentSign = 1
                elif A[j] < A[j-1]:
                    currentSign = -1
                else: 
                    break
                if currentSign != sign:
                    currentSize += 1
                    sign = currentSign
                else:
                    break
            totalSize = max(totalSize, currentSize)
            i += 1
        return totalSize
                
                    


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        
        n = len(A)
        if n == 1:
            return 1
        
        dp = [[1, 1] for i in range(n)]
        ans = 1

        for i in range(1, n):
            if A[i] > A[i - 1]:
                dp[i][0] += dp[i - 1][1]
            if A[i] < A[i - 1]:
                dp[i][1] += dp[i - 1][0]
            ans = max(ans, dp[i][0], dp[i][1])

        return ans


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        i = 0
        k = 1
        count = 0
        N = len(A)
        ans = 0
        anchor = 0
        # for i in range(1, N):
        #     c = self.cmp(A[i-1], A[i])
        #     if c == 0:
        #         anchor = i
        #     elif i == N-1 or c * self.cmp(A[i], A[i+1]) != -1:
        #         ans = max(ans, i - anchor + 1)
        #         anchor = i
        max1 =0
        while i <= k and k < len(A):
            # print((A[k-1] > A[k] and k % 2 != 0) and (A[k-1] < A[k] and k % 2 == 0))
            # print(A[k-1], A[k])
            if (A[k-1] > A[k] and k % 2 == 0):
                count += 1
                # print(A[k])
                k += 1
                
            elif (A[k-1] < A[k] and k % 2 != 0):
                count += 1
                # print(A[k])
                k += 1
                
            else:
                i = k
                k = i+1
                max1 = max(max1,count)
                count = 0
        max1 = max(max1,count) + 1
        # print(count)
        i = 0
        k = 1
        max2 = 0
        count = 0
        while i <= k and k < len(A):
            if (A[k-1] > A[k] and k % 2 != 0): 
                count += 1
                k += 1
            elif (A[k-1] < A[k] and k % 2 == 0):
                count += 1
                k += 1
            else:
                i += 1
                k = i+1
                max2 = max(max2,count)
                count = 0
        max2 = max(max2,count) + 1
        print((max1, max2))
        return max(max1, max2)
            
            
        # return ans 


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        global_max_sub = 1
        local_max = 1
        pre_diff = 0
        
        for i in range(1, len(A)):
            cur_diff = A[i] - A[i-1]
            
            mul = cur_diff * pre_diff
            
            if cur_diff == 0:
                local_max = 1
            elif mul < 0:
                local_max += 1
            else:
                local_max = 2
                
            if local_max > global_max_sub:
                global_max_sub = local_max
            
            pre_diff = cur_diff
            
        return global_max_sub
            


class Solution:
    def compare(self,m,n):
        if(m<n):
            return -1
        elif(m>n):
            return 1
        else:
            return 0
        
    def maxTurbulenceSize(self, A: List[int]) -> int:
        N = len(A)
        ans = 1
        anchor = 0

        for i in range(1, N):
            c = self.compare(A[i-1], A[i])
            if c == 0:
                anchor = i
            elif i == N-1 or c * self.compare(A[i], A[i+1]) != -1:
                    ans = max(ans, i - anchor + 1)
                    anchor = i
        return ans
    
#     def maxTurbulenceSize(self, A: List[int]) -> int:
#         deviate=0
#         ans=1
#         for i in range(1,len(A)):
#             c=self.compare(A[i-1],A[i])
#             if(c==0):
#                 deviate=1
#             elif i==len(A)-1 or c*self.compare(A[i],A[i+1])!=-1:
#                 ans = max(ans, i - deviate + 1)
#                 deviate = i
#         return ans


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        #Longest, dp, or memoisation
        
        if(len(A)==0):return 0
        if(len(A)==1):return 1
        max_t=1
        sgn=0 #1: next array should be larger, -1:smaller, 0:new
        current_l=0
        i=0
        while True:      
            #print(A[i],current_l,sgn)
            if(sgn==1 and A[i]>A[i-1]):
                sgn=-sgn
                current_l+=1 
            elif(sgn==-1 and A[i]<A[i-1]):
                sgn=-sgn
                current_l+=1              
            elif(sgn==0):
                current_l=1
                if(i < len(A)-1):
                    if(A[i+1]>A[i]):
                        sgn=1
                    elif(A[i+1]<A[i]):
                        sgn=-1
                    else:
                        sgn=0                
            else:
                i+=-1 #back!
                max_t=max(current_l,max_t)
                current_l=1
                if(i < len(A)-1):
                    if(A[i+1]>A[i]):
                        sgn=1
                    elif(A[i+1]<A[i]):
                        sgn=-1
                    else:
                        sgn=0
                else:
                    #already end
                    max_t = max(max_t,1)   
            i+=1
            if(i==len(A)):
                break
        max_t=max(current_l,max_t) 
        return max_t
        
                    
                    
                
            


class Solution:
    def __init__(self):
        self.lmemo = {}
        self.gmemo = {}
        
    def maxTurbulenceSize(self, A: List[int]) -> int:
        def rmtsl(pos):
            if pos not in self.lmemo:
                self.lmemo[pos] = 1 + (rmtsg(pos+1) if A[pos] < A[pos+1] else 0)
            return self.lmemo[pos]
        def rmtsg(pos):
            if pos not in self.gmemo:
                self.gmemo[pos] = 1 + (rmtsl(pos+1) if A[pos] > A[pos+1] else 0)
            return self.gmemo[pos]
        self.lmemo[len(A)-1] = self.gmemo[len(A)-1] = 1
        return max([max(rmtsl(i),rmtsg(i)) for i in range(len(A)-1,-1,-1)])

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        run = 1
        last_diff = 0
        last = A[0]
        best = 1
        for a in A[1:]:
            diff = last - a
            if diff == 0:
                run = 1
            elif diff * last_diff < 0:
                run += 1
            else:
                run = 2
            best = max(run, best)
            last_diff = diff
            last = a
        return best
        


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        maxAB, currA, currB = 1, 1, 1  # 初始化

        for i in range(1, len(A)):
            if A[i] > A[i - 1]:  # 以第 i 个元素结尾，呈现升序的情况
                currA = currB + 1
                currB = 1
            elif A[i] < A[i - 1]:  # 以第 i 个元素结尾，呈现降序的情况
                currB = currA + 1
                currA = 1
            else:
                currA, currB = 1, 1  # 出现相等的情况，重新计数

            maxAB = max(maxAB, currA, currB)  # 更新最优值

        return maxAB


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        i = 0
        k = 1
        count = 0
        N = len(A)
        ans = 0
        anchor = 0
        # for i in range(1, N):
        #     c = self.cmp(A[i-1], A[i])
        #     if c == 0:
        #         anchor = i
        #     elif i == N-1 or c * self.cmp(A[i], A[i+1]) != -1:
        #         ans = max(ans, i - anchor + 1)
        #         anchor = i
        max1 =0
        while i <= k and k < len(A):
            # print((A[k-1] > A[k] and k % 2 != 0) and (A[k-1] < A[k] and k % 2 == 0))
            # print(A[k-1], A[k])
            if (A[k-1] > A[k] and k % 2 == 0):
                count += 1
                # print(A[k])
                k += 1
                
            elif (A[k-1] < A[k] and k % 2 != 0):
                count += 1
                # print(A[k])
                k += 1
                
            else:
                i = k
                k = i+1
                max1 = max(max1,count)
                count = 0
        max1 = max(max1,count) + 1
        # print(count)
        i = 0
        k = 1
        max2 = 0
        count = 0
        while i <= k and k < len(A):
            if (A[k-1] > A[k] and k % 2 != 0): 
                count += 1
                k += 1
            elif (A[k-1] < A[k] and k % 2 == 0):
                count += 1
                k += 1
            else:
                i += 1
                k = i+1
                max2 = max(max2,count)
                count = 0
        max2 = max(max2,count) + 1
        return max(max1, max2)
            
            
        # return ans 


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        result = 1
        left = 0
        def cmp(a, b):
            return (a > b) - (a < b)
        for i in range(1, len(A)):
            if A[i] == A[i-1]:
                left = i
            elif i == len(A) -1 or cmp(A[i],A[i-1])*cmp(A[i+1],A[i]) != -1:
                result = max(result, i+1-left)
                left = i
        return result


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        dp = [0] * len(A)
        for i in range(1, len(A)):
            if A[i] == A[i - 1]: continue
            dp[i] = 1 if A[i] > A[i - 1] else -1
        res = 0
        for i in range(1, len(A)):
            if dp[i] == 0:
                curr = 0
                continue
            curr = curr + 1 if dp[i] + dp[i - 1] == 0 else 1
            res = max(res, curr)
        return res + 1


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) == 1:
            return 1
        
        sign = -(A[1] - A[0])
        max_length = 1
        cur_length = 1
        for i in range(1, len(A)):
            # print(A[i - 1], A[i], \" -- \", cur_length, sign)
            
            if A[i-1] < A[i] and sign < 0:
                cur_length += 1
            elif A[i - 1] > A[i] and sign > 0:
                cur_length += 1
            else:
                max_length = max(max_length, cur_length)
                if A[i - 1] != A[i]:
                    cur_length = 2
                else:
                    cur_length = 1
                
            sign = A[i] - A[i - 1]
                
            
        
        max_length = max(max_length, cur_length)
        
        return max_length


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        res=clen=0
        
        for i in range(len(A)):
            if i>=2 and (A[i-2]>A[i-1]<A[i] or A[i-2]<A[i-1]>A[i]):
                clen+=1
            elif i>=1 and A[i-1]!=A[i]:
                clen=2
            else:
                clen=1
            res=max(res,clen)
        return res
                
                    


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        maxLength = 0
        length = 0
        
        for i in range(len(A)):
            if i >= 2 and ( A[i - 2] > A[i - 1] < A[i] or A[i - 2] < A[i - 1] > A[i]):
                length += 1
            elif i >= 1 and A[i - 1] != A[i]:
                length = 2
            else:
                length = 1
            maxLength = max(maxLength, length)
        
        return maxLength

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) <= 1:
            return len(A)
        
        current_len = max_len = 0
        prev_less = prev_great = True
        
        for i in range(1, len(A)):
            if A[i-1] > A[i] and prev_less:
                current_len += 1
                prev_less = False
                prev_great = True
            elif A[i-1] < A[i] and prev_great:
                current_len += 1
                prev_less = True
                prev_great = False
            else:
                max_len = max(max_len, current_len + 1)
                if A[i-1] > A[i]:
                    current_len = 1
                    prev_less = False
                    prev_great = True
                elif A[i-1] < A[i]:
                    current_len = 1
                    prev_less = True
                    prev_great = False
                else:
                    current_len = 0
                    prev_less = prev_great = True
                    
        return max(max_len, current_len + 1)


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        res = curr = 0
        for i in range(len(A)):
            if i >= 2 and (A[i-2] > A[i-1] < A[i] or A[i-2] < A[i-1] > A[i]):
                curr += 1
            elif i >= 1 and A[i-1] != A[i]:
                curr = 2
            else:
                curr = 1
            res = max(res, curr)
        return res

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        ##for each index k, we will find the largest array that is turbulent where we consider cases being ending with a decrease, and ending with an increase.
        currentTurb = [1,1]##indicates ending on decrease, ending on increase
        maxTurb = max(currentTurb)
        ALength = len(A)
        for i in range(1,ALength):
            currentNum = A[i]
            previousNum = A[i-1]##be careful about what you are calling previous (check indices)
            a,b = currentTurb
            if currentNum > previousNum:
                currentTurb = [1,a+1]
            elif currentNum < previousNum:##don't forget to specify elif
                currentTurb = [b+1,1]
            else:
                currentTurb = [1,1]##since we can't have any turbulence now
            maxTurb = max(max(currentTurb),maxTurb)
        return maxTurb

class Solution:
    def maxTurbulenceSize(self, A):
        
        ans = 0 
        cnt = 0
        
        for i in range(len(A)):
            
            if i >= 2 and (A[i-2]<A[i-1]>A[i] or A[i-2]>A[i-1]<A[i] ):
                cnt += 1
            elif i >=1 and A[i-1] != A[i]:
                cnt = 2
            else:
                cnt = 1
                
            ans = max(ans,cnt)
            
        return ans

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        res, l, b, log = 1, 1, A[0], -1
        for a in A[1:]:
            if a == b: log, l = -1, 1
            elif a > b:
                if log != 1: l += 1
                else: l = 2
                log = 1
            else:
                if log != 0: l += 1
                else: l = 2
                log = 0
            res, b = max(res, l), a
        return res


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) == 1:
            return 1
        max_len = 1
        temp_len = 1
        odd_or_even = None
        last = A[0]
        for i in A[1:]:
            if i == last:
                odd_or_even = None
                temp_len = 1
                continue
            elif i > last:
                if odd_or_even == None or odd_or_even == 1:
                    odd_or_even = 0
                    temp_len += 1
                else:
                    odd_or_even = 0
                    temp_len = 2
            else:
                if odd_or_even == None or odd_or_even == 0:
                    odd_or_even = 1
                    temp_len += 1
                else:
                    odd_or_even = 1
                    temp_len = 2
            last = i
            max_len = max(max_len, temp_len)
        return max_len


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        n = len(A)
        dp = [0] * n
        for i in range(1, n):
            if A[i] > A[i - 1]:
                dp[i] = 1
            elif A[i] < A[i - 1]:
                dp[i] = -1
        res = 0
        for i in range(1, n):
            if dp[i] == 0:
                curr = 0
                continue
            if dp[i] + dp[i - 1] != 0:
                curr = 1
            else:
                curr += 1
            res = max(res, curr)
        return res + 1


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        n = len(A)
        inc = [1 for _ in range(n)]
        dec = [1 for _ in range(n)]

        for i in range(1, len(A)):
            if A[i-1]<A[i]:
                inc[i] = dec[i-1] + 1
                dec[i] = 1
            elif A[i-1]>A[i]:
                dec[i] = inc[i-1] + 1
                inc[i] = 1
            else:
                inc[i]=1
                dec[i]=1
        return max(max(inc), max(dec))


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(set(A)) == 1:
            return 1
        a, b  = (1,-1)[A[0] < A[1]], (1,-1)[A[-1] > A[-2]]   
        A.extend([A[-1] + a,A[0] - b]) 
        A[0], A[1:] = A[-1], A[0:-1]
        ct = 0
        totalct = []
        i = 1
        while i < len(A) - 1:
            a, b, c = A[i-1], A[i], A[i+1]
            if (b > a) == (b > c) and b not in [a,c]:
                ct += 1
            else:
                if ct + 1 == i:
                    totalct.append(ct + 1)
                else:
                    totalct.append(ct + 2)
                ct = 0
            i += 1 
        if totalct:
            ct += 1
        totalct.append(ct)
        return max(totalct)


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) == 1:
            return 1
        diff=0
        ret = 1
        max_ret = ret
        for i in range(len(A)-1):
            _diff=(A[i+1]-A[i])
            if diff*_diff <0:
                ret+=1
            else: 
                max_ret = max(ret,max_ret)
                if _diff == 0:
                    ret = 1
                else:
                    ret = 2
            diff = _diff
        return max(ret,max_ret)

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) == 0:
            return 0
        elif len(A) == 1:
            return 1
        elif len(A) == 2 and A[1] == A[0]:
            return 1
        breaks = []
        for i in range(len(A)-1):
            if A[i] == A[i+1]:
                breaks.append((i,i+1))
            if i-1 >= 0 and A[i-1] < A[i] and i+1 < len(A) and A[i] < A[i+1]:
                breaks.append((i,i))
            elif i-1 >= 0 and A[i-1] > A[i] and i+1 < len(A) and A[i] > A[i+1]:
                breaks.append((i,i))
        sorted_breaks = sorted(breaks, key=lambda t: t[0])
        lengths = []
        for i,t in enumerate(sorted_breaks):
            if i == 0:
                lengths.append(t[0]-0+1)
            else:
                lengths.append(t[0]-sorted_breaks[i-1][1] + 1)
        if len(sorted_breaks):
            lengths.append(len(A) - sorted_breaks[-1][1])
        else:
            lengths.append(len(A))
        if len(lengths):     
            return max(lengths)
        else:
            return 0

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if len(A) <= 1:
            return len(A)
                                            
        memo =  [2 * [1] for _ in range(len(A) + 1)]
        res = 1
        
        for i in range(1, len(A)):
            for sign in range(2):
                if A[i] != A[i-1] and int(A[i] > A[i-1]) == sign:
                    memo[i][sign] = max(memo[i][sign], 1 + memo[i-1][(sign + 1) % 2])
                    res = max(res, memo[i][sign])
        
        return res

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        j, ans = 0, 1
        for i, a in enumerate(A[1:], 1):
            if A[i] == A[i - 1]:
                j = i
            elif i == len(A) - 1 or not (A[i - 1] > A[i] < A[i + 1] or A[i - 1] < A[i] > A[i + 1]):
                ans = max(ans, i - j + 1)
                j = i
        return ans

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        if not A: return 0
        n = len(A)
        if n == 1:
            return 1
        
        dp = [1 for _ in range(n)]
        dp[1] = 2 if A[0] != A[1] else 1
        maxTurb = dp[1]
        wasGreater = A[0] > A[1]  # Was the last comparison greater or not.
        
        for i in range(1, n):
            if A[i-1] > A[i] and not wasGreater:
                wasGreater = True
                dp[i] += dp[i-1]
            elif A[i-1] < A[i] and wasGreater:
                wasGreater = False
                dp[i] += dp[i-1]
            else:
                dp[i] = 2 if A[i] != A[i-1] else 1
                
            maxTurb = max(maxTurb, dp[i])
        return maxTurb


class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        i, j = 0, 1
        res = 1
        while j < len(A) - 1:
            if A[i] == A[j] and i + 1 == j: # [100, 100, 100]
                # print('i:', i, 'A[i]:', A[i])
                # print('j:', j, 'A[j]:', A[j])
                i = j
                j += 1
            else:
                j += 1
                sign1, sign2 = 0, 0 # 0 for > and 1 for <
                if A[j] == A[j - 1] or A[j - 1] == A[j - 2]:
                    pass
                    # print('i:', i, 'A[i]:', A[i])
                    # print('j:', j, 'A[j]:', A[j])
                else:
                    if A[j] < A[j - 1]:
                        sign1 = 1
                    if A[j - 1] < A[j - 2]:
                        sign2 = 1
                if sign1 == sign2:
                    # print('i:', i, 'A[i]:', A[i])
                    # print('j:', j, 'A[j]:', A[j])
                    if j - i > res:
                        res = j - i
                    i = j - 1
        if j - i > res:
            # print('i:', i, 'A[i]:', A[i])
            # print('j:', j, 'A[j]:', A[j])
            res = j - i + 1
        return res