Find the length of the longest subsequence whose consecutive differences strictly alternate between positive and negative.
Problem
Given an integer array nums, find the length of the longest subsequence that forms a wiggle sequence.
A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.
A sequence is a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference may be either positive or negative. A sequence with one element is also considered a wiggle sequence.
Your task is to return the maximum possible length of such a subsequence.
Notes
- Equal adjacent values do not contribute to a wiggle.
- You may skip elements to maximize the length.
Input Format
- A single integer array
nums. nums[i]is an integer value.
Output Format
- Return a single integer: the length of the longest wiggle subsequence.
Constraints
- The answer is at least
1when the array is non-empty. - Equal consecutive values do not create a wiggle.
- A valid solution should work in linear time or close to linear time.
Example 1
Input
nums = [1,7,4,9,2,5]
Output
6
Explanation
The entire array alternates up and down: 1→7 (up), 7→4 (down), 4→9 (up), 9→2 (down), 2→5 (up).
Example 2
Input
nums = [1,17,5,10,13,15,10,5,16,8]
Output
7
Explanation
One optimal wiggle subsequence is [1,17,5,10,5,16,8]. Its differences alternate positive and negative.
Show 1 more example
Example 3
Input
nums = [1,2,3,4,5]
Output
2
Explanation
Any two distinct numbers form a wiggle subsequence, but longer subsequences never alternate in sign.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.