420. The Longest Zigzag

A sequence ZIGZAGS when its consecutive differences alternate between positive and negative, with no difference equal to zero. A single element zigzags, and so does any two distinct elements.

Print the length of the longest zigzagging subsequence.

1 7 4 9 2 5 -> 6 the whole sequence already zigzags 1 2 3 4 5 -> 2 any two adjacent, and no more

The obstacle is that whether an element may be appended depends on the DIRECTION of the last step, not on the last value. So one running length is not enough.

Carry two:

up the longest zigzag so far whose last step went UP down the longest zigzag so far whose last step went DOWN

Then each element updates exactly one of them:

if a[i] > a[i-1]: up = down + 1 if a[i] < a[i-1]: down = up + 1 if equal: neither changes

and the answer is the larger.

That works on ADJACENT comparisons alone, without considering skipped elements, and the reason is worth pausing on. A run of increases contributes only its last element to an upward step, because extending an existing upward run never helps; and the value that ends the longest downward zigzag is always available as a starting point. Skipping is therefore already accounted for.

Equal neighbours must change nothing, which is why 2 2 answers 1 and 3 3 3 2 5 answers 3.

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