Solution to TopCoder ZigZag.

Let \(A\) an array of length of \(n\) of integers. Let \(Z(i,0)\) be the longest zig-zag subsequence *ending* at index \(i\) with a positive difference (the second last element of it is strictly less than the last element), and let \(Z(i,1)\) be the longest zig-zag subsequence *ending* at index \(i\) with a negative difference. Then:

\[ \begin{align*} Z(i,0) &= \min_{j < i, \\ A[j] < A[i] } (Z(j,1) + 1) \\ Z(i,1) &= \min_{j < i, A[j] > A[i] } (Z(j,0) + 1) \\ Z(0,0) &= 1 \\ Z(0,1) &= 1 \end{align*} \]

Java solution: