Longest Zigzag Subsequence — Solution & Editorial

Back to the Problem

Greedy/DP pair (up, down): a rise extends the best falling sequence and vice versa; equal neighbours change nothing.

Complexity: O(N)