463. The Longest Zigzag Run

A CONTIGUOUS run is a zigzag when the comparisons between neighbours alternate: up, down, up, down, and so on, or the reverse. Equal neighbours break a zigzag, because equality is neither up nor down.

Print the length of the longest zigzag run. A single element is a zigzag of length 1.

9 4 2 10 7 8 8 1 9 -> 5 the run 4 2 10 7 8 4 8 12 16 -> 2 the comparisons never alternate

Problem #420 asks the same question about SUBSEQUENCES. Contiguity changes the answer from a table to two running counters, which is the point of comparing them.

The state has to record HOW the run arrived, because what may follow depends on the direction of the last step:

up length of the longest zigzag ending here with a[i] > a[i-1] down length of the longest zigzag ending here with a[i] < a[i-1]

Each one extends the other, never itself:

a[i] > a[i-1] -> up = down_before + 1, down = 1 a[i] < a[i-1] -> down = up_before + 1, up = 1 a[i] == a[i-1] -> up = 1, down = 1

The counter that does not apply resets to 1 rather than carrying forward, since a run ending in an up step cannot also be described as ending in a down step.

The equality case is worth its own line. 1 2 2 1 answers 2, not 4: the middle comparison is neither direction, so the run is cut there. A solution that tests only > and < and leaves the counters untouched otherwise will jump the gap and report 4.

Constraints - `1 ≤ n ≤ 200000` - `-1000000 ≤ value ≤ 1000000`