Longest Wiggle Subsequence
Advanced
A wiggle sequence has differences between neighbours that alternate between positive and negative (a single value, or two different values, also count). Return the length of the longest wiggle subsequence of nums (a subsequence keeps the order but may skip values).
For [1, 7, 4, 9, 2, 5] the answer is 6; for [1, 17, 5, 10, 13, 15, 10, 5, 16, 8] it is 7.
The starter code compares every value with all earlier ones. It is correct but too slow for long lists.
Examples
Example 1
Input:
wiggle_length([1, 7, 4, 9, 2, 5])
Output:
6
Example 2
Input:
wiggle_length([1, 17, 5, 10, 13, 15, 10, 5, 16, 8])
Output:
7
Constraints
0 <= len(nums) <= 2000000 <= nums[i] <= 10**9
Theory
Go to TheoryKeywords
dsa-sheetgreedygreedy-strategies
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.