Given an array nums of n positive integers. The task is to find the longest Zig-Zag subsequence problem such that all elements of this are alternating (nums_{i-1} < nums_{i} > nums_{i+1} or nums_{i-1} > nums_{i} < nums_{i+1}).
 
Example 1:
Input: nums = {1,5,4}
Output: 3
Explanation: The entire sequenece is a 
Zig-Zag sequence.
Examplae 2:
Input: nums = {1,17,5,10,13,15,10,5,16,8}
Ooutput: 7
Explanation: There are several subsequences
that achieve this length. 
One is {1,17,10,13,10,16,8}.
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function ZigZagMaxLength() which takes the sequence  nums as input parameter and returns the maximum length of alternating sequence.
Expected Time Complexity: O(n)
Expected Space Complexity: O(1)
Constraints:
1 <= n <= 10^{5}

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Starter code:
#Initial Template for Python 3
class Solution:
	def ZigZagMaxLength(self, nums):
		# Code here
		

Solutions:
class Solution:

	def ZigZagMaxLength(self, nums):
		inc = 1
		dec = 1
		for i in range(1, len(nums)):
			if nums[i] > nums[i - 1]:
				inc = dec + 1
			elif nums[i] < nums[i - 1]:
				dec = inc + 1
		return max(inc, dec)


class Solution:

	def ZigZagMaxLength(self, nums):
		if not nums:
			return 0
		length = 1
		up = None
		for i in range(1, len(nums)):
			if nums[i] > nums[i - 1] and up != True:
				length += 1
				up = True
			if nums[i] < nums[i - 1] and up != False:
				length += 1
				up = False
		return length


class Solution:

	def ZigZagMaxLength(self, nums):
		prevsign = 0
		leng = 1

		def help(num):
			if num != 0:
				if num > 0:
					return 1
				else:
					return -1
			else:
				return 0
		for i in range(1, len(nums)):
			sign = help(nums[i] - nums[i - 1])
			if sign != 0 and sign != prevsign:
				prevsign = sign
				leng += 1
		return leng


class Solution:

	def ZigZagMaxLength(self, nums):
		length = 1
		last_sign = 0

		def help(n):
			if n != 0:
				if n > 0:
					return 1
				else:
					return -1
			else:
				return 0
		for i in range(1, len(nums)):
			sign = help(nums[i] - nums[i - 1])
			if sign != 0 and sign != last_sign:
				last_sign = sign
				length += 1
		return length


class Solution:

	def ZigZagMaxLength(self, arr):
		(up, down) = (1, 1)
		for i in range(1, n):
			if arr[i] > arr[i - 1]:
				up = down + 1
			elif arr[i] < arr[i - 1]:
				down = up + 1
		return max(up, down)


class Solution:

	def ZigZagMaxLength(self, nums):
		in1 = 1
		d = 1
		for i in range(1, len(nums)):
			if nums[i - 1] < nums[i]:
				in1 = d + 1
			elif nums[i - 1] > nums[i]:
				d = in1 + 1
		return max(in1, d)


class Solution:

	def ZigZagMaxLength(self, nums):
		if len(nums) < 2:
			return len(nums)
		up = 1
		down = 1
		for i in range(1, len(nums)):
			if nums[i] > nums[i - 1]:
				up = down + 1
			elif nums[i] < nums[i - 1]:
				down = up + 1
		return max(up, down)


class Solution:

	def ZigZagMaxLength(self, arr):
		n = len(arr)
		length = 1
		lastsign = 0

		def sinfun(n):
			if n != 0:
				if n > 0:
					return 1
				else:
					return -1
			else:
				return 0
		for i in range(1, n):
			sign = sinfun(arr[i] - arr[i - 1])
			if sign != lastsign and sign != 0:
				lastsign = sign
				length += 1
		return length


class Solution:

	def ZigZagMaxLength(self, nums):

		def signFun(num):
			if num != 0:
				if num > 0:
					return 1
				else:
					return -1
			else:
				return 0
		n = len(nums)
		length = 1
		lastSign = 0
		for i in range(1, n):
			sign = signFun(nums[i] - nums[i - 1])
			if sign != lastSign and sign != 0:
				length += 1
				lastSign = sign
		return length


class Solution:

	def ZigZagMaxLength(self, nums):
		a = 1
		b = 1
		for i in range(1, len(nums)):
			if nums[i] > nums[i - 1]:
				a = b + 1
			elif nums[i] < nums[i - 1]:
				b = a + 1
		return max(a, b)


class Solution:

	def ZigZagMaxLength(self, nums):
		(l, r) = (1, 1)
		for i in range(1, len(nums)):
			if nums[i] > nums[i - 1]:
				l = r + 1
			elif nums[i] < nums[i - 1]:
				r = l + 1
		return max(l, r)


class Solution:

	def ZigZagMaxLength(self, a):
		(p1, p2) = (a[0], a[0])
		(f1, f2) = (True, False)
		n = len(a)
		(a1, a2) = (1, 1)
		for i in range(1, n):
			if f1:
				if p1 < a[i]:
					a1 += 1
					f1 = False
			elif p1 > a[i]:
				a1 += 1
				f1 = True
			if f2:
				if p2 < a[i]:
					a2 += 1
					f2 = False
			elif p2 > a[i]:
				a2 += 1
				f2 = True
			p1 = a[i]
			p2 = a[i]
		return max(a1, a2)


class Solution:

	def ZigZagMaxLength(self, nums):
		prev1 = nums[0]
		prev2 = nums[0]
		(g, s, ans1, ans2) = (0, 1, 1, 1)
		for i in range(len(nums)):
			if not g and nums[i] > prev1:
				ans1 += 1
				g = 1
			elif g and nums[i] < prev1:
				g = 0
				ans1 += 1
			if not s and nums[i] > prev2:
				ans2 += 1
				s = 1
			elif s and nums[i] < prev2:
				s = 0
				ans2 += 1
			prev1 = nums[i]
			prev2 = nums[i]
		return max(ans1, ans2)


class Solution:

	def ZigZagMaxLength(self, nums):
		set = 0
		c = 1
		start = 0
		for j in range(len(nums) - 1):
			if nums[j] > nums[j + 1]:
				set = 1
				break
				start = j
			if nums[j] < nums[j + 1]:
				set = 0
				break
				start = j
		for i in range(start, len(nums)):
			if nums[i] > nums[i - 1]:
				if set == 0:
					c += 1
					set = 1
			elif nums[i] < nums[i - 1]:
				if set == 1:
					c += 1
					set = 0
		return c


class Solution:

	def ZigZagMaxLength(self, l):
		prev = l[0]
		c = 0
		ans1 = 1
		ans2 = 1
		for i in range(len(l)):
			if c == 0:
				if l[i] > prev:
					prev = l[i]
					c = 1
					ans1 += 1
				else:
					prev = l[i]
			elif l[i] < prev:
				c = 0
				prev = l[i]
				ans1 += 1
			else:
				prev = l[i]
		prev = l[0]
		c = 1
		for i in range(len(l)):
			if c == 0:
				if l[i] > prev:
					prev = l[i]
					c = 1
					ans2 += 1
				else:
					prev = l[i]
			elif l[i] < prev:
				c = 0
				prev = l[i]
				ans2 += 1
			else:
				prev = l[i]
		return max(ans1, ans2)


class Solution:

	def ZigZagMaxLength(self, nums):
		prev = nums[0]
		(g, ans1) = (0, 1)
		for i in range(1, len(nums)):
			if not g and nums[i] > prev:
				ans1 += 1
				g = 1
			elif g and nums[i] < prev:
				g = 0
				ans1 += 1
			prev = nums[i]
		prev = nums[0]
		(g, ans2) = (1, 1)
		for i in range(1, len(nums)):
			if not g and nums[i] > prev:
				ans2 += 1
				g = 1
			elif g and nums[i] < prev:
				g = 0
				ans2 += 1
			prev = nums[i]
		return max(ans1, ans2)


class Solution:

	def ZigZagMaxLength(self, a):
		p = a[0]
		f = True
		n = len(a)
		(a1, a2) = (1, 1)
		for i in range(1, n):
			if f:
				if p < a[i]:
					a1 += 1
					f = False
				p = a[i]
			else:
				if p > a[i]:
					a1 += 1
					f = True
				p = a[i]
		p = a[0]
		f = False
		for i in range(1, n):
			if f:
				if p < a[i]:
					a2 += 1
					f = False
				p = a[i]
			else:
				if p > a[i]:
					a2 += 1
					f = True
				p = a[i]
		return max(a1, a2)


class Solution:

	def ZigZagMaxLength(self, a):
		if len(a) == 1:
			return 1
		c = 0
		ans = 1
		if a[0] > a[1]:
			c = 1
		for i in range(len(a) - 1):
			if c == 0:
				if a[i + 1] > a[i]:
					ans += 1
					c = 1
			elif c == 1:
				if a[i + 1] < a[i]:
					ans += 1
					c = 0
		return ans


class Solution:

	def ZigZagMaxLength(self, nums):
		i = 1
		j = 1
		if len(nums) == 1:
			return 1
		for x in range(1, len(nums)):
			if nums[x] > nums[x - 1]:
				i = j + 1
			elif nums[x] < nums[x - 1]:
				j = i + 1
		return max(i, j)


class Solution:

	def ZigZagMaxLength(self, nums):
		if len(nums) == 1:
			return 1
		diff = []
		for i in range(1, len(nums)):
			diff.append(nums[i] - nums[i - 1])
		c = 0
		for num in diff:
			if num > 0:
				flag = 0
				c = 1
				break
			elif num < 0:
				flag = 1
				c = 1
				break
		for i in range(1, len(diff)):
			num = diff[i]
			if num < 0 and flag == 0:
				c += 1
				flag ^= 1
			elif num > 0 and flag == 1:
				c += 1
				flag ^= 1
			else:
				continue
		return c + 1


class Solution:

	def ZigZagMaxLength(self, nums):
		increase = 0
		decrease = 0
		for i in range(1, len(nums)):
			if nums[i] > nums[i - 1]:
				increase = 1 + decrease
			elif nums[i] < nums[i - 1]:
				decrease = 1 + increase
		return max(increase, decrease) + 1


class Solution:

	def ZigZagMaxLength(self, nums):
		n = len(nums)
		if n <= 1:
			return n
		max_up = max_down = 1
		for i in range(1, n):
			if nums[i] > nums[i - 1]:
				max_up = max(max_up, max_down + 1)
			elif nums[i] < nums[i - 1]:
				max_down = max(max_down, max_up + 1)
		return max(max_up, max_down)


def signum(n):
	if n > 0:
		return 1
	if n < 0:
		return -1
	if n == 0:
		return 0

class Solution:

	def ZigZagMaxLength(self, nums):
		l = 1
		lsign = 0
		for i in range(1, len(nums)):
			sign = signum(nums[i] - nums[i - 1])
			if sign != lsign and sign != 0:
				lsign = sign
				l += 1
		return l


class Solution:

	def ZigZagMaxLength(self, nums):
		temp = [1]
		count = [1]
		n = len(nums)
		for i in range(1, n):
			if nums[i] > nums[i - 1]:
				temp.append(count[i - 1] + 1)
				count.append(count[i - 1])
			elif nums[i] < nums[i - 1]:
				count.append(temp[i - 1] + 1)
				temp.append(temp[i - 1])
			elif nums[i] == nums[i - 1]:
				temp.append(temp[i - 1])
				count.append(count[i - 1])
		return max(count[-1], temp[-1])


class Solution:

	def ZigZagMaxLength(self, nums):
		return zz(nums)

def zz(a):
	n = len(a)
	if n == 1:
		return 1
	pd = a[1] - a[0]
	l = 0 if pd == 0 else 1
	for i in range(2, n):
		diff = a[i] - a[i - 1]
		if diff != 0 and diff * pd <= 0:
			l += 1
			pd = diff
	return l + 1


class Solution:

	def ZigZagMaxLength(self, nums):
		mmax = [1]
		mmin = [1]
		n = len(nums)
		for i in range(1, n):
			if nums[i] > nums[i - 1]:
				mmax.append(mmin[i - 1] + 1)
				mmin.append(mmin[i - 1])
			elif nums[i] < nums[i - 1]:
				mmin.append(mmax[i - 1] + 1)
				mmax.append(mmax[i - 1])
			elif nums[i] == nums[i - 1]:
				mmax.append(mmax[i - 1])
				mmin.append(mmin[i - 1])
		return max(mmin[-1], mmax[-1])


class Solution:

	def ZigZagMaxLength(self, nums):
		r = 1
		s = 0
		for i in range(1, n):
			if s == 0:
				if nums[i] > nums[i - 1]:
					s = 1
					r += 1
				if nums[i] < nums[i - 1]:
					s = -1
					r += 1
			if s > 0:
				if nums[i] < nums[i - 1]:
					s = -1
					r += 1
			elif nums[i] > nums[i - 1]:
				s = 1
				r += 1
		return r


class Solution:

	def ZigZagMaxLength(self, nums):
		start = 1
		end = 1
		for i in range(len(nums) - 1):
			if nums[i] > nums[i + 1]:
				start = end + 1
			elif nums[i] < nums[i + 1]:
				end = start + 1
		return max(start, end)


class Solution:

	def ZigZagMaxLength(self, a):
		n = len(a)
		(ma, mi) = (1, 1)
		for i in range(1, n):
			if a[i] > a[i - 1]:
				ma = mi + 1
			elif a[i] < a[i - 1]:
				mi = ma + 1
		return max(ma, mi)


import sys

class Solution:

	def signum(self, n):
		if n == 0:
			return 0
		else:
			return 1 if n > 0 else -1

	def ZigZagMaxLength(self, arr):
		(length, last_sign) = (1, 0)
		for i in range(1, n):
			sign = self.signum(arr[i] - arr[i - 1])
			if sign != last_sign and sign != 0:
				length = length + 1
				last_sign = sign
		return length


class Solution:

	def ZigZagMaxLength(self, nums):
		c = [[0, 0] for i in range(len(nums))]
		c[0] = [1, 'A']
		for i in range(1, len(nums)):
			if nums[i] < nums[i - 1]:
				s = 'N'
			elif nums[i] > nums[i - 1]:
				s = 'P'
			else:
				c[i][0] = c[i - 1][0]
				c[i][1] = c[i - 1][1]
				continue
			j = i - 1
			while j > -1 and c[j][1] != s:
				if j == 0:
					break
				j -= 1
			c[i][0] = c[j][0] + 1
			c[i][1] = 'P' if s == 'N' else 'N'
		return c[-1][0]


class Solution:

	def ZigZagMaxLength(self, a):

		def check(n):
			if n == 0:
				return 0
			elif n > 0:
				return 1
			else:
				return -1
		n = len(a)
		if n == 0:
			return 0
		ans = 1
		lastsign = 0
		for i in range(1, n):
			sign = check(a[i] - a[i - 1])
			if sign != lastsign and sign != 0:
				ans += 1
				lastsign = sign
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.ZigZagMaxLength(A))


class Solution:

	def ZigZagMaxLength(self, a):
		inc = 1
		dec = 1
		for i in range(1, n):
			if a[i] > a[i - 1]:
				dec = inc + 1
			elif a[i] < a[i - 1]:
				inc = dec + 1
		return max(inc, dec)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.ZigZagMaxLength(A))


class Solution:

	def ZigZagMaxLength(self, nums):
		up = 1
		down = 1
		if len(nums) <= 1:
			return len(nums)
		for i in range(len(nums) - 1):
			if nums[i] < nums[i + 1]:
				up = down + 1
			elif nums[i] > nums[i + 1]:
				down = up + 1
		return max(up, down)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.ZigZagMaxLength(A))


class Solution:

	def ZigZagMaxLength(self, nums):
		df = []
		if len(nums) < 2:
			return len(nums)
		for j in range(1, len(nums)):
			l1 = nums[j]
			l2 = nums[j - 1]
			if l1 == l2:
				df.append(0)
			elif l1 < l2:
				df.append(-1)
			else:
				df.append(1)
		c = 1
		prev = 0
		for t in df:
			if t == 0:
				continue
			elif t != prev:
				c += 1
				prev = t
			else:
				continue
		return c
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.ZigZagMaxLength(A))


class Solution:

	def ZigZagMaxLength(self, l):
		u = 0
		d = 0
		n = len(l)
		for i in range(n - 1):
			if l[i + 1] > l[i]:
				u = d + 1
			elif l[i + 1] < l[i]:
				d = u + 1
		return max(u, d) + 1


class Solution:

	def ZigZagMaxLength(self, nums):
		ct1 = 1
		up = 1
		last = nums[0]
		for i in range(1, n):
			if up:
				if nums[i] > last:
					last = nums[i]
					ct1 += 1
					up = 0
				else:
					last = nums[i]
			elif nums[i] < last:
				last = nums[i]
				ct1 += 1
				up = 1
			else:
				last = nums[i]
		ct2 = 1
		up = 0
		last = nums[0]
		for i in range(1, n):
			if up:
				if nums[i] > last:
					last = nums[i]
					ct2 += 1
					up = 0
				else:
					last = nums[i]
			elif nums[i] < last:
				last = nums[i]
				ct2 += 1
				up = 1
			else:
				last = nums[i]
		return max(ct1, ct2)


class Solution:

	def ZigZagMaxLength(self, nums):
		if len(nums) == 1:
			return 1
		count = 1
		up = None
		for i in range(1, len(nums)):
			if nums[i] > nums[i - 1] and up != True:
				count += 1
				up = True
			elif nums[i] < nums[i - 1] and up != False:
				count += 1
				up = False
		return count


class Solution:

	def ZigZagMaxLength(self, nums):
		n = len(nums)
		choice = None
		length = 1
		if n < 2:
			return length
		if n >= 2:
			i = 1
			while i < n and nums[i] == nums[i - 1]:
				i += 1
			if i < n:
				if nums[i] > nums[i - 1]:
					choice = 0
					length += 1
				elif nums[i] < nums[i - 1]:
					choice = 1
					length += 1
		for j in range(i + 1, n):
			if nums[j] > nums[j - 1] and choice == 1:
				length += 1
				choice = 0
			elif nums[j] < nums[j - 1] and choice == 0:
				length += 1
				choice = 1
		return length


class Solution:

	def ZigZagMaxLength(self, nums):
		lastsign = 0
		count = 1
		for i in range(1, len(nums)):
			sign = nums[i] - nums[i - 1]
			if sign > 0:
				sign = 1
			elif sign < 0:
				sign = -1
			else:
				sign = 0
			if sign != lastsign and sign != 0:
				count += 1
				lastsign = sign
		return count


class Solution:

	def signum(self, n):
		if n != 0:
			return 1 if n > 0 else -1
		else:
			return 0

	def ZigZagMaxLength(self, nums):
		n = len(nums)
		if n == 0:
			return 0
		lastSign = 0
		length = 1
		for i in range(1, n):
			Sign = self.signum(nums[i] - nums[i - 1])
			if Sign != lastSign and Sign != 0:
				lastSign = Sign
				length += 1
		return length


class Solution:

	def ZigZagMaxLength(self, nums):
		n = len(nums)
		count = 1
		lastSign = 0
		for i in range(1, n):
			val = nums[i] - nums[i - 1]
			sign = 0
			if val > 0:
				sign = 1
			elif val < 0:
				sign = -1
			if sign != 0 and sign != lastSign:
				lastSign = sign
				count += 1
		return count