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

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Amortized analysis

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:
		(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
			elif 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
			cnt += 1
		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)
			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)
		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
			elif 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):
		if A.count(A[0]) == len(A):
			return 1
		if len(A) < 2:
			return len(A)
		start = 0
		end = 0
		max_res = 0
		while end < len(A) - 1:
			if (A[end - 1] - A[end]) * (A[end] - A[end + 1]) < 0:
				end += 1
			else:
				max_res = max(max_res, end - start + 1)
				start = end
				end = start + 1
		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)
			elif 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(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 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:
		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:
		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:

		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:
		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
			elif 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 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
		return max(max(dp_GT), max(dp_LT))


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)
		dp = [0 for _ in range(len(A))]
		dp[0] = 1
		dp[1] = 2 if A[1] != A[0] else 1
		for i in range(2, len(A)):
			if A[i - 2] > A[i - 1] < A[i] or A[i - 2] < A[i - 1] > A[i]:
				dp[i] = dp[i - 1] + 1
			elif 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)
		curr_max = global_max = 1
		for i in range(1, len(A)):
			if i >= 2 and A[i - 2] > A[i - 1] < A[i] or A[i - 2] < A[i - 1] > A[i]:
				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:
		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)):
			if i % 2 == 1:
				if A[i] > A[i - 1]:
					length += 1
				else:
					longest = max(length, longest)
					length = 1
			elif i % 2 == 0:
				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)):
			if i % 2 == 1:
				if A[i] < A[i - 1]:
					length += 1
				else:
					longest2 = max(length, longest2)
					length = 1
			elif i % 2 == 0:
				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


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:

	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]
			if cur <= 0 and prev <= 0 or (cur >= 0 and prev >= 0):
				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
					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))]
		for i in range(len(A))[::-1]:
			if i == len(A) - 1:
				dp_grid[i] = [1, 1]
			elif 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:
		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)
			res = max(res, dp[i][0], dp[i][1])
		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:
		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:
		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
			elif 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]
		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:
			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:
		i = 0
		k = 1
		count = 0
		N = len(A)
		ans = 0
		anchor = 0
		max1 = 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 = k
				k = i + 1
				max1 = max(max1, count)
				count = 0
		max1 = max(max1, count) + 1
		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)


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


class Solution:

	def maxTurbulenceSize(self, A: List[int]) -> int:
		if len(A) == 0:
			return 0
		if len(A) == 1:
			return 1
		max_t = 1
		sgn = 0
		current_l = 0
		i = 0
		while True:
			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
				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:
					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]:
				currA = currB + 1
				currB = 1
			elif A[i] < A[i - 1]:
				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:
		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:
		if len(A) == 1:
			return 1
		sign = -(A[1] - A[0])
		max_length = 1
		cur_length = 1
		for i in range(1, len(A)):
			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:
		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:
		currentTurb = [1, 1]
		maxTurb = max(currentTurb)
		ALength = len(A)
		for i in range(1, ALength):
			currentNum = A[i]
			previousNum = A[i - 1]
			(a, b) = currentTurb
			if currentNum > previousNum:
				currentTurb = [1, a + 1]
			elif currentNum < previousNum:
				currentTurb = [b + 1, 1]
			else:
				currentTurb = [1, 1]
			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:
		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
			elif 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:
		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:
		(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:
		(i, j) = (0, 1)
		res = 1
		while j < len(A) - 1:
			if A[i] == A[j] and i + 1 == j:
				i = j
				j += 1
			else:
				j += 1
				(sign1, sign2) = (0, 0)
				if A[j] == A[j - 1] or A[j - 1] == A[j - 2]:
					pass
				else:
					if A[j] < A[j - 1]:
						sign1 = 1
					if A[j - 1] < A[j - 2]:
						sign2 = 1
				if sign1 == sign2:
					if j - i > res:
						res = j - i
					i = j - 1
		if j - i > res:
			res = j - i + 1
		return res