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.

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
     def wiggleMaxLength(self, arr):
         """
         :type nums: List[int]
         :rtype: int
         """
         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):
         """
         :type nums: List[int]
         :rtype: int
         """
         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):
         """
         :type nums: List[int]
         :rtype: int
         """
         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 # all equal
             
         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):
         """
         :type nums: List[int]
         :rtype: int
         """
         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):
         """
         :type nums: List[int]
         :rtype: int
         """
         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):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) == 0:
             return 0
         if len(nums) == 1:
             return 1
         N = len(nums)
         sol = [0 for _ in nums]
         sol[0] = [1,1] #starting with -, starting with +
         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):
         """
         :type nums: List[int]
         :rtype: int
         """
         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):
         """
         :type nums: List[int]
         :rtype: int
         """
         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
             else:
                 if nums[i] < two:
                     two = nums[i]
                 else:
                     one = two
                     two = nums[i]
                     cnt += 1
         return cnt

class Solution:
     def wiggleMaxLength(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         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):
         """
         :type nums: List[int]
         :rtype: int
         """
         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])
             else:
                 if nums[i]>seq[-1]:
                     seq[-1] = nums[i]
                 else:
                     seq.append(nums[i])
         return len(seq)

class Solution:
     def wiggleMaxLength(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         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