Wiggle Subsequence

Medium · Greedy · about 15 minutes

Asked at Google, Amazon, Microsoft, Meta.

A sequence *wiggles* when the differences between neighbors keep switching sign: up, down, up, … or down, up, down, … (zero differences aren't allowed). A single value counts, and so do two unequal values. Pick a subsequence of nums that wiggles and is as long as possible; return its length.