Wiggle Subsequence
Medium · Greedy · Array · Dynamic Programming · Greedy
Problem
A wiggle sequence is one where the differences between consecutive elements strictly alternate between positive and negative. The first difference may have either sign. A single element, or two unequal elements, also count as wiggle sequences; any zero difference breaks the pattern.
Given an integer array nums, return the length of its longest subsequence that is a wiggle sequence. A subsequence keeps the original order but may skip elements.
Examples
Input: nums = [2,6,3,8,4] Output: 5
The differences +4, -3, +5, -4 already alternate, so all five elements are kept.
Input: nums = [1,4,7,2,5,5,3] Output: 5
For example 1, 7, 2, 5, 3: the 4 sits inside a climb and one 5 is a repeat.
Input: nums = [3,3,3] Output: 1
Every difference is zero, so only one element can be kept.
Constraints
- 1 <= len(nums) <= 1000
- 0 <= nums[i] <= 1000
Approaches
- Quadratic DP over the last element — time O(n²), space O(n)
Follow-up
The answer is also the number of "turns" in the array plus one, after merging equal neighbors: each run of rises keeps only its peak, each run of falls only its valley. The use cases fix the first move to a rise and count the deletions instead of the kept elements.
Related problems
Start free on Cariara · Coding problems · System design studio
