# ZigZag sequence without dynamic programming

I just came across the maximum zigzag sequence problem, defined as follows:

A zigzag sequence is defined as a sequence of numbers such that the difference between two consecutive numbers alternates between positive and negative.

Given a an array of N integer number, find the length of the longest zigzag subsequence. A subsequence is formed by deleting zero or more elements of the original sequence, but preserving the order in the original sequence.

For example given the array {1, 2, 4, 2, 3, 5, 1} the subsequence {1, 4, 2, 5, 1} is the longest zigzag.

A sequence of one element is a trivial zigzag of length 1.

I've found several references to a dynamic programming formulation of the solution which is O(N^2) and very complex. See for example this.

However, I've come with a much simpler solution with O(N) and based on finding all the local maximum and minimum of the original sequence, that is, the elements of which the sign of the difference between consecutive elements change. Here is the code in Java:

public static int zigZagLength_pablochacin(int[] sequence) {

if (sequence.length == 0)
return 0;

int lastDiff = 0;
int length = 1;

for (int i = 1; i < sequence.length; i++) {
int diff = Integer.signum(sequence[i] - sequence[i - 1]);
if ((diff != 0) && (diff != lastDiff)) {
lastDiff = diff;
length++;
}
}

return length;
}


Apparently,this approach has also been proposed elsewhere.

My question is, am I missing something that makes this simple solution wrong?

Note: I originally asked this question in Code review Stack, but was considered off-topic, as it doesn't relate to code style but to the solution.

• "if (sequence.length = 0)" - I presume you retyped this?
– TLW
May 8, 2017 at 1:20
• This is not the same thing as saying this solution is correct, but I ran this solution (ported to C) and fuzzed it against the "standard" solution with AFL for 15 minutes (thus far) without it hitting any case where the two came out with different results.
– TLW
May 8, 2017 at 1:47
• Thanks for testing @TLW. And no, that was a huge bug in my code. :-( May 8, 2017 at 20:40

In fact, you have proved the correctness of your algorithm basically since your algorithm is, as you have written, based on finding all the local maximum and minimum of the original sequence. The simple mathematical reason is that for each zigzag, i.e., $$a[i]a[i+2]$$ or $$a[i]>a[i+1], there must exist a local maximum or a local minimum respectively.