All problems

Wiggle Subsequence

Medium · greedy

Look at the differences between each pair of neighbouring numbers in a list. The list is a wiggle if those differences are all non-zero and alternate in sign: up, down, up, down, ... or down, up, down, up, ... A list with one number is a wiggle, and a list with two numbers is a wiggle if they are different.

Given a list of integers nums, you may delete any numbers you like (possibly none) and keep the rest in their original order. Return the length of the longest wiggle you can keep.

Examples

Example 1

Input: nums = [3, 8, 5, 5, 9, 1, 4]

Output: 6

Delete one of the two 5s. Then 3, 8, 5, 9, 1, 4 goes up, down, up, down, up.

Example 2

Input: nums = [4, 4, 4]

Output: 1

Every difference is zero, so only a single number can be kept.

Example 3

Input: nums = [1, 2, 3, 4, 5]

Output: 2

The list only rises. Any two different numbers form a wiggle, but a third would repeat the same direction.

Constraints