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.

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top