A sequence {x1, x2, .. xn} is alternating sequence if its elements satisfy one of the following relations :
x1 < x2 > x3 < x4 > x5..... or  x1 >x2 < x3 > x4 < x5.....
Your task is to find the longest such sequence.
Example 1:
Input: nums = {1,5,4}
Output: 3
Explanation: The entire sequenece is a 
alternating sequence.
Examplae 2:
Input: nums = {1,17,5,10,13,15,10,5,16,8}
Output: 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 AlternatingaMaxLength() 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}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

	def AlternatingaMaxLength(self, nums):

		# Code here

Solutions:
class Solution:

	def AlternatingaMaxLength(self, nums):
		stateMap = [[0 for i in range(2)] for _ in range(len(nums))]
		(stateMap[0][0], stateMap[0][1]) = (1, 1)
		for i in range(1, len(nums)):
			if nums[i] > nums[i - 1]:
				stateMap[i][0] = max(stateMap[i - 1][1] + 1, stateMap[i - 1][0])
				stateMap[i][1] = stateMap[i - 1][1]
			elif nums[i] < nums[i - 1]:
				stateMap[i][0] = stateMap[i - 1][0]
				stateMap[i][1] = max(stateMap[i - 1][0] + 1, stateMap[i - 1][1])
			else:
				stateMap[i][0] = stateMap[i - 1][0]
				stateMap[i][1] = stateMap[i - 1][1]
		return max(stateMap[-1])


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def AlternatingaMaxLength(self, nums):
		n = len(nums)
		if n == 1:
			return 1
		dp = [[0, -1] for _ in range(n)]
		new_dp = None
		dp[-1] = [1, -1]
		if nums[-1] > nums[-2]:
			dp[-2] = [2, 0]
		elif nums[-1] < nums[-2]:
			dp[-2] = [2, 1]
		elif nums[-1] == nums[-2]:
			new_dp = [[0, -1] for _ in range(n)]
			dp[-2] = [1, 1]
			new_dp[-2] = [1, 0]
		for i in range(n - 3, -1, -1):
			if nums[i + 1] > nums[i]:
				if dp[i + 1][1] == 1:
					dp[i] = [dp[i + 1][0] + 1, 0]
				else:
					dp[i] = dp[i + 1]
			elif nums[i + 1] < nums[i]:
				if dp[i + 1][1] == 0:
					dp[i] = [dp[i + 1][0] + 1, 1]
				else:
					dp[i] = dp[i + 1]
			elif nums[i + 1] == nums[i]:
				dp[i] = dp[i + 1]
		if new_dp:
			for i in range(n - 3, -1, -1):
				if nums[i + 1] > nums[i]:
					if new_dp[i + 1][1] == 1:
						new_dp[i] = [new_dp[i + 1][0] + 1, 0]
					else:
						new_dp[i] = new_dp[i + 1]
				elif nums[i + 1] < nums[i]:
					if new_dp[i + 1][1] == 0:
						new_dp[i] = [new_dp[i + 1][0] + 1, 1]
					else:
						new_dp[i] = new_dp[i + 1]
				elif nums[i + 1] == nums[i]:
					new_dp[i] = new_dp[i + 1]
		if new_dp:
			return max(new_dp[0][0], dp[0][0])
		else:
			return dp[0][0]


class Solution:

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


class Solution:

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


class Solution:

	def AlternatingaMaxLength(self, nums):
		i = 0
		flag = 0
		count = 0
		if len(nums) > 1:
			if nums[1] < nums[0]:
				flag = 1
		else:
			return 1
		while i < len(nums) - 1:
			if flag:
				if nums[i + 1] >= nums[i]:
					i += 1
					continue
				else:
					count += 1
					flag = 0
			elif nums[i + 1] <= nums[i]:
				i += 1
				continue
			else:
				count += 1
				flag = 1
		return count + 1


class Solution:

	def AlternatingaMaxLength(self, nums):
		n = len(nums)
		maxi = mini = 1
		for i in range(1, n):
			if nums[i] > nums[i - 1]:
				maxi = mini + 1
			elif nums[i] < nums[i - 1]:
				mini = maxi + 1
			else:
				continue
		return max(mini, maxi)


class Solution:

	def AlternatingaMaxLength(self, nums):
		minel = 1
		maxel = 1
		for i in range(1, len(nums)):
			if nums[i] > nums[i - 1]:
				maxel = minel + 1
			elif nums[i] < nums[i - 1]:
				minel = maxel + 1
			else:
				continue
		return max(maxel, minel)


class Solution:

	def AlternatingaMaxLength(self, arr):
		ans1 = 1
		ans2 = 1
		for i in range(1, len(arr)):
			if arr[i] > arr[i - 1]:
				ans1 = ans2 + 1
			elif arr[i - 1] > arr[i]:
				ans2 = ans1 + 1
		return max(ans1, ans2)


class Solution:

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


class Solution:

	def AlternatingaMaxLength(self, A):

		def sign(v):
			return 0 if v == 0 else 1 if v > 0 else -1

		def _solve(dir):
			(ans, v) = (1, A[0])
			for i in range(1, n):
				if dir == sign(A[i] - v):
					ans += 1
					dir = -dir
				v = A[i]
			return ans
		return max(_solve(1), _solve(-1))


class Solution:

	def AlternatingaMaxLength(self, A):
		from math import copysign

		def _solve(dir):
			(ans, v) = (1, A[0])
			for i in range(1, n):
				if A[i] != v and dir == copysign(1, A[i] - v):
					ans += 1
					dir = -dir
				v = A[i]
			return ans
		return max(_solve(1), _solve(-1))


class Solution:

	def AlternatingaMaxLength(self, nums):
		ans = 1
		dir = 0
		for i in range(1, len(nums)):
			if nums[i] - nums[i - 1] > 0 and dir <= 0:
				ans += 1
				dir = 1
			elif nums[i] - nums[i - 1] < 0 and dir >= 0:
				ans += 1
				dir = -1
		return ans


class Solution:

	def AlternatingaMaxLength(self, nums):
		(inn, out) = (1, 1)
		for i in range(1, len(nums)):
			if nums[i - 1] > nums[i]:
				inn = out + 1
			elif nums[i - 1] == nums[i]:
				pass
			else:
				out = inn + 1
		return max(inn, out)


class Solution:

	def AlternatingaMaxLength(self, nums):
		(m1, m2) = (1, 1)
		for i in range(1, n):
			if nums[i] > nums[i - 1]:
				m1 = m2 + 1
			if nums[i] < nums[i - 1]:
				m2 = m1 + 1
		return max(m1, m2)


class Solution:

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


class Solution:

	def AlternatingaMaxLength(self, nums):
		stack = [nums.pop()]
		while nums:
			if nums[-1] == stack[-1]:
				nums.pop()
			elif len(stack) == 1:
				stack.append(nums.pop())
			elif stack[-2] < stack[-1] > nums[-1]:
				stack.append(nums.pop())
			elif stack[-2] > stack[-1] < nums[-1]:
				stack.append(nums.pop())
			else:
				stack.pop()
				stack.append(nums.pop())
		return len(stack)


class Solution:

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


class Solution:

	def AlternatingaMaxLength(self, nums):
		minn = 1
		maxx = 1
		for i in range(1, n):
			if nums[i] < nums[i - 1]:
				minn = maxx + 1
			elif nums[i] > nums[i - 1]:
				maxx = minn + 1
		return max(minn, maxx)


class Solution:

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


class Solution:

	def AlternatingaMaxLength(self, arr):
		dp = [[0 for i in range(len(arr))] for j in range(2)]
		(dp[0][-1], dp[1][-1], ans) = (1, 1, 1)
		for i in range(len(arr) - 2, -1, -1):
			if arr[i] > arr[i + 1]:
				dp[0][i] = 1 + dp[1][i + 1]
				dp[1][i] = dp[1][i + 1]
			if arr[i] < arr[i + 1]:
				dp[1][i] = 1 + dp[0][i + 1]
				dp[0][i] = dp[0][i + 1]
			if arr[i] == arr[i + 1]:
				(dp[0][i], dp[1][i]) = (dp[0][i + 1], dp[1][i + 1])
		ans = max(dp[0][0], dp[1][0])
		return ans


class Solution:

	def AlternatingaMaxLength(self, nums):
		(prev_lt_sz, prev_gt_sz) = (1, 1)
		for i in range(1, len(nums)):
			if nums[i] > nums[i - 1]:
				prev_gt_sz = prev_lt_sz + 1
			if nums[i] < nums[i - 1]:
				prev_lt_sz = prev_gt_sz + 1
		return max(prev_lt_sz, prev_gt_sz)


class Solution:

	def AlternatingaMaxLength(self, nums):

		def func(inc):
			i = 1
			max_alt = 0
			prev = nums[0]
			count1 = 1
			while i < len(nums):
				if inc:
					if nums[i] > prev:
						inc = False
						prev = nums[i]
						count1 += 1
						i += 1
					else:
						while i < len(nums) and nums[i] <= nums[i - 1]:
							i += 1
						i -= 1
						if i != len(nums):
							prev = nums[i]
							i += 1
				elif nums[i] < prev:
					prev = nums[i]
					inc = True
					count1 += 1
					i += 1
				else:
					while i < len(nums) and nums[i] >= nums[i - 1]:
						i += 1
					i -= 1
					if i != len(nums):
						prev = nums[i]
						i += 1
			return count1
		count1 = func(True)
		count2 = func(False)
		return max(count1, count2)


class Solution:

	def solve(self, arr, now):
		n = len(arr)
		ans = 1
		for i in range(1, n):
			if now == 1:
				if arr[i] < arr[i - 1]:
					now = 0
					ans += 1
			elif arr[i] > arr[i - 1]:
				now = 1
				ans += 1
		return ans

	def AlternatingaMaxLength(self, arr):
		return max(self.solve(arr, 1), self.solve(arr, 0))


class Solution:

	def AlternatingaMaxLength(self, nums):
		mx = 1
		mn = 1
		for i in range(1, len(nums)):
			if nums[i] > nums[i - 1]:
				mx = mn + 1
			if nums[i] < nums[i - 1]:
				mn = mx + 1
		return max(mx, mn)


class Solution:

	def AlternatingaMaxLength(self, nums):
		cnt = 1
		arr = nums
		mini = nums[0]
		maxi = nums[0]
		mode = -1
		for i in range(1, n):
			if mode == -1:
				if arr[i] > mini:
					mode = 1
					cnt += 1
					mini = maxi = arr[i]
				if arr[i] < maxi:
					mode = 0
					cnt += 1
					mini = maxi = arr[i]
			elif mode == 1 and arr[i] < maxi or (mode == 0 and arr[i] > mini):
				mode = 1 - mode
				cnt += 1
				mini = maxi = arr[i]
			else:
				maxi = max(maxi, arr[i])
				mini = min(mini, arr[i])
		return cnt


class Solution:

	def AlternatingaMaxLength(self, nums):
		if len(nums) <= 2:
			return len(nums)
		else:
			l = nums
			ans = 2 if l[1] != l[0] else 1
			inc = l[1] > l[0]
			n = len(l)
			for i in range(2, n):
				if inc:
					if l[i] >= l[i - 1]:
						continue
					else:
						inc = not inc
						ans += 1
				elif l[i] <= l[i - 1]:
					continue
				else:
					inc = not inc
					ans += 1
			return ans


def solve(nums, idx, large, dp):
	if idx == len(nums):
		return 0
	if dp[idx][large] != -1:
		return dp[idx][large]
	if large:
		if nums[idx] > nums[idx - 1]:
			dp[idx][large] = 1 + solve(nums, idx + 1, 0, dp)
		else:
			dp[idx][large] = solve(nums, idx + 1, 1, dp)
	elif nums[idx] < nums[idx - 1]:
		dp[idx][large] = 1 + solve(nums, idx + 1, 1, dp)
	else:
		dp[idx][large] = solve(nums, idx + 1, 0, dp)
	return dp[idx][large]

class Solution:

	def AlternatingaMaxLength(self, nums):
		n = len(nums)
		l1 = 1
		l2 = 0
		dp = [[0 for _ in range(2)] for _ in range(n + 1)]
		for idx in range(1, n):
			for large in range(2):
				if large:
					if nums[idx] > nums[idx - 1]:
						dp[idx][large] = 1 + dp[idx - 1][0]
					else:
						dp[idx][large] = dp[idx - 1][1]
				elif nums[idx] < nums[idx - 1]:
					dp[idx][large] = 1 + dp[idx - 1][1]
				else:
					dp[idx][large] = dp[idx - 1][0]
		return max(dp[n - 1][0], dp[n - 1][1]) + 1


class Solution:

	def AlternatingaMaxLength(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 AlternatingaMaxLength(self, nums):
		c = 1
		f = 0
		for i in range(1, len(nums)):
			if f == 0:
				if nums[i] > nums[i - 1]:
					c += 1
					f = 1
				if c == 1 and nums[i] != nums[i - 1]:
					c += 1
					f = 0
			elif nums[i] < nums[i - 1]:
				c += 1
				f = 0
		return c


class Solution:

	def AlternatingaMaxLength(self, nums):
		ma = 1
		mi = 1
		for i in range(1, len(nums)):
			if nums[i] > nums[i - 1]:
				ma = mi + 1
			elif nums[i] < nums[i - 1]:
				mi = ma + 1
			else:
				continue
		return max(ma, mi)


class Solution:

	def util(self, arr, n):
		if n == 0:
			return 0

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


class Solution:

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


class Solution:

	def AlternatingaMaxLength(self, nums):
		n = len(nums)
		if n == 1:
			return 1
		flag = -1
		count = 0
		max_length = 0
		i = 1
		while i < n:
			while nums[i] == nums[i - 1] and i < n - 1:
				i += 1
			if i == n - 1 and nums[n - 1] == nums[n - 2]:
				return max_length
			if nums[i] > nums[i - 1]:
				if flag == 0:
					count += 1
					flag = 1
				elif flag == -1:
					flag = 1
					count += 2
			elif flag == 1:
				count += 1
				flag = 0
			elif flag == -1:
				flag = 0
				count += 2
			i += 1
			max_length = max(max_length, count)
		return max_length


class Solution:

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


class Solution:

	def AlternatingaMaxLength(self, A):
		incr = 1
		decr = 1
		for i in range(1, len(A)):
			if A[i] > A[i - 1]:
				incr = decr + 1
			elif A[i] < A[i - 1]:
				decr = incr + 1
		return max(incr, decr)


class Solution:

	def AlternatingaMaxLength(self, nums):
		flag = 0
		ele = nums[0]
		count = 1
		for i in range(1, len(nums)):
			if nums[i] > ele:
				ele = nums[i]
				if flag != 1:
					flag = 1
					count += 1
			elif nums[i] < ele:
				ele = nums[i]
				if flag != -1:
					flag = -1
					count += 1
		return count


class Solution:

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