313. Wiggle Subsequence
A sequence wiggles when the differences between consecutive picks flip sign at every step and are never zero. [1, 7, 4, 9, 2, 5] wiggles, because its differences (6, -3, 5, -7, 3) alternate up, down, up, down. A sequence with fewer than two elements wiggles trivially, and a two-element sequence wiggles whenever its two values differ. A difference of 0 breaks the pattern — the alternation must be strict, and the very first difference may be either positive or negative.
You are given an array of integers nums. A subsequence is what remains after deleting any number of elements (possibly none) without reordering the ones you keep.
Return the length of the longest subsequence of nums that wiggles, as a single integer.
Can you solve it in one pass with O(1) extra space?
Example 1:
Input: nums = [1, 7, 4, 9, 2, 5]
Output: 6
Explanation: The whole array already wiggles: the differences (6, -3, 5, -7, 3) alternate sign at every step, so no deletions are needed.
Example 2:
Input: nums = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]
Output: 7
Explanation: One longest choice keeps [1, 17, 10, 13, 10, 16, 8], whose differences (16, -7, 3, -13, 6, -8) alternate sign. No wiggle subsequence of length 8 exists.
Example 3:
Input: nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Output: 2
Explanation: Every step rises, so at most one rise can be kept — any two elements form the longest wiggle subsequence.
Constraints:
- 1 ≤ nums.length ≤ 1000
- 0 ≤ nums[i] ≤ 1000
Hints:
Deleting elements only ever removes 'flat' steps or merges runs that move in the same direction. So think per index: what is the longest wiggle ending here whose final step went up? Whose final step went down?
Those two quantities only depend on their values at the previous index. Keep two counters `up` and `down`: when nums[i] > nums[i-1], set up = down + 1; when nums[i] < nums[i-1], set down = up + 1; when equal, change nothing. One pass, O(1) space.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 7, 4, 9, 2, 5]
Expected output: 6