A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence. 

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Examples:

Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.

Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Input: [1,2,3,4,5,6,7,8,9]
Output: 2



Follow up:
Can you do it in O(n) time?


Credits:Special thanks to @agave and @StefanPochmann for adding this problem and creating all test cases.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

Greedy algorithms

Starter code: class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        

Solutions:
class Solution:

	def wiggleMaxLength(self, arr):
		n = len(arr)
		if n < 2:
			return n
		wsl = [0] * n
		wsl[0] = 1
		for cur in range(1, n):
			prev = cur - 1
			if arr[cur] > arr[prev] and wsl[prev] <= 1:
				wsl[cur] = abs(wsl[prev]) + 1
			elif arr[cur] < arr[prev] and wsl[prev] > 0:
				wsl[cur] = (abs(wsl[prev]) + 1) * -1
			else:
				wsl[cur] = wsl[prev]
		return abs(wsl[n - 1])


class Solution:

	def wiggleMaxLength(self, nums):
		n = len(nums)
		if n < 2:
			return n
		prev_diff = nums[1] - nums[0]
		count = 2 if prev_diff != 0 else 1
		for i in range(2, n):
			diff = nums[i] - nums[i - 1]
			if diff > 0 and prev_diff <= 0 or (diff < 0 and prev_diff >= 0):
				count += 1
				prev_diff = diff
		return count


class Solution:

	def wiggleMaxLength(self, nums):
		if len(nums) < 2:
			return len(nums)
		diffs = []
		for i in range(1, len(nums)):
			diffs.append(nums[i] - nums[i - 1])
		prev_idx = 0
		while diffs[prev_idx] == 0:
			prev_idx += 1
			if prev_idx == len(diffs):
				return 1
		cnt = 2
		for i in range(prev_idx + 1, len(diffs)):
			if diffs[prev_idx] * diffs[i] < 0:
				cnt += 1
				prev_idx = i
		return cnt


class Solution:

	def wiggleMaxLength(self, nums):
		if len(nums) == 0:
			return 0
		max_up = [1]
		max_down = [1]
		for i in range(1, len(nums)):
			if nums[i] > nums[i - 1]:
				max_up.append(max_down[i - 1] + 1)
				max_down.append(max_down[i - 1])
			elif nums[i] < nums[i - 1]:
				max_up.append(max_up[i - 1])
				max_down.append(max_up[i - 1] + 1)
			else:
				max_up.append(max_up[i - 1])
				max_down.append(max_down[i - 1])
		return max(max_up[-1], max_down[-1])


class Solution:

	def wiggleMaxLength(self, nums):
		if not nums:
			return 0
		l = len(nums)
		dp = [0] * l
		up = [0] * l
		down = [0] * l
		up[0] = down[0] = 1
		for i in range(1, l):
			if nums[i - 1] < nums[i]:
				up[i] = up[i - 1]
				down[i] = up[i - 1] + 1
			elif nums[i - 1] > nums[i]:
				down[i] = down[i - 1]
				up[i] = down[i - 1] + 1
			else:
				up[i] = up[i - 1]
				down[i] = down[i - 1]
		return max(down[-1], up[-1])


class Solution:

	def wiggleMaxLength(self, nums):
		if len(nums) == 0:
			return 0
		if len(nums) == 1:
			return 1
		N = len(nums)
		sol = [0 for _ in nums]
		sol[0] = [1, 1]
		for i in range(1, N):
			new = [0, 0]
			if nums[i] > nums[i - 1]:
				new[0] = sol[i - 1][1] + 1
			else:
				new[0] = sol[i - 1][0]
			if nums[i] < nums[i - 1]:
				new[1] = sol[i - 1][0] + 1
			else:
				new[1] = sol[i - 1][1]
			sol[i] = new
		return max(sol[-1])


class Solution:

	def wiggleMaxLength(self, nums):
		n = len(nums)
		if n == 0:
			return 0
		gn = [1] * n
		trend = 0
		for i in range(1, n):
			prev = nums[i - 1]
			if prev == nums[i]:
				gn[i] = gn[i - 1]
			else:
				if trend == 0:
					gn[i] = gn[i - 1] + 1
					trend = 1 if nums[i] > prev else -1
					continue
				if nums[i] > prev and trend == -1 or (nums[i] < prev and trend == 1):
					gn[i] = gn[i - 1] + 1
					trend = -trend
				else:
					gn[i] = gn[i - 1]
		return gn[-1]


class Solution:

	def wiggleMaxLength(self, nums):
		l = len(nums)
		if l == 0:
			return 0
		elif l == 1:
			return 1
		st = 1
		while nums[0] == nums[st]:
			st += 1
			if st == l:
				return 1
		(one, two) = (nums[0], nums[st])
		cnt = 2
		for i in range(st + 1, l):
			if nums[i] == two:
				continue
			if one < two:
				if nums[i] > two:
					two = nums[i]
				else:
					one = two
					two = nums[i]
					cnt += 1
			elif nums[i] < two:
				two = nums[i]
			else:
				one = two
				two = nums[i]
				cnt += 1
		return cnt


class Solution:

	def wiggleMaxLength(self, nums):
		if nums == []:
			return 0
		if len(nums) < 2:
			return 1
		max_length = 1
		state = 0
		i = 1
		while i < len(nums):
			while state == 0 and i < len(nums):
				if nums[i - 1] > nums[i]:
					max_length = max_length + 1
					state = 2
				if nums[i - 1] < nums[i]:
					max_length = max_length + 1
					state = 1
				i = i + 1
			while state == 1 and i < len(nums):
				if nums[i - 1] > nums[i]:
					max_length = max_length + 1
					state = 2
				i = i + 1
			while state == 2 and i < len(nums):
				if nums[i - 1] < nums[i]:
					state = 1
					max_length = max_length + 1
				i = i + 1
		return max_length


class Solution:

	def wiggleMaxLength(self, nums):
		l = len(nums)
		if l == 0:
			return 0
		elif l == 1:
			return 1
		st = 1
		while nums[0] == nums[st]:
			st += 1
			if st == l:
				return 1
		seq = [nums[0], nums[st]]
		for i in range(st + 1, l):
			if nums[i] == seq[-1]:
				continue
			if seq[-1] < seq[-2]:
				if nums[i] < seq[-1]:
					seq[-1] = nums[i]
				else:
					seq.append(nums[i])
			elif nums[i] > seq[-1]:
				seq[-1] = nums[i]
			else:
				seq.append(nums[i])
		return len(seq)


class Solution:

	def wiggleMaxLength(self, nums):
		nums = [nums[i] for i in range(len(nums)) if i == 0 or nums[i] != nums[i - 1]]
		print(nums)
		total = min(2, len(nums))
		for i in range(1, len(nums) - 1):
			if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
				total += 1
			elif nums[i] < nums[i - 1] and nums[i] < nums[i + 1]:
				total += 1
		return total