ZigZag sequence without dynamic programming

Question

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.

• TLW: "if (sequence.length = 0)" - I presume you retyped this?
• TLW: 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.
• pablochacin: Thanks for testing @TLW. And no, that was a huge bug in my code. :-(

Answer 1

Your simple algorithm is correct.

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+1]>a[i+2]$ or $a[i]>a[i+1]<a[i+2]$, there must exist a local maximum or a local minimum respectively.

A more rigorous and rather tedious proof is needed to convince all of us that there is no off-by-one error in your program. However, I will skip it since it is routine and not enlightening at all.