A signal monitor records n samples. A wiggle run is a subsequence whose consecutive differences strictly alternate between positive and negative (up, down, up, ... or down, up, down, ...). A single sample is a wiggle run of length 1, and two samples with different values form one of length 2. Report the length of the longest wiggle run that can be selected as a subsequence (elements keep their original order but need not be adjacent).
Line 1: an integer n.
Line 2: n space-separated integers, the samples in order.
A single integer: the length of the longest wiggle subsequence.
Example 1
Input
6 1 7 4 9 2 5
Expected
6
Explanation
The whole sequence wiggles: 1<7>4<9>2<5, so the longest wiggle subsequence has length 6.
Example 2
Input
4 3 3 3 3
Expected
1
Explanation
All samples are equal, so there is never a strict up or down move; the longest wiggle run is a single element, length 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →