Wiggle Subsequence

The key idea

Only the direction of each consecutive difference matters. A new element extends the wiggle exactly when its difference flips the sign of the previous one. So the answer is the number of direction changes plus one, which one greedy pass can count.

Problem

A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if it exists) may be either positive or negative. A sequence with one element or two unequal 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) alternate in sign. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences: the first has two consecutive positive differences, and the second has its last difference equal to 0.

A subsequence is obtained by deleting some (possibly zero) elements from the original sequence while leaving the remaining elements in their original order.

Given an integer array nums, return the length of the longest wiggle subsequence of nums.

Constraints

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

Examples

Input: nums = [1,7,4,9,2,5] Output: 6

Input: nums = [1,17,5,10,13,15,10,5,16,8] Output: 7

Input: nums = [1,2,3,4,5,6,7,8,9] Output: 2

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →