# TopCoder Longest ZigZag Subsequence

#### Posted on November 28, 2013

##### Last updated on November 28, 2013

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:

Markdown SHA1: 78cdfd42f02c0b91a65776233fddbc05cd98faed