Longest zig-zag subsequence using dynamic programming

Question

I need to write a method that needs to return the length of the longest subsequence of sequence that is a zig-zag sequence. The algorithmic approach should be dynamic programming.

---

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative.

Eg - 1,7,4,9,2,5   is a zig-zag sequence
because the differences (6,-3,5,-7,3) are alternately positive and negative. 

1,4,7,2,5 is not a zig-zag sequence.

---

My Code:

---

public static int longestZigZag(int[] seq){

    int len = seq.length;
    int[] count= new int[len];

    for(int i=0;i<len;i++)
        count[i]=1;

    for(int i=1;i<len;i++){
        int k = (int)Math.pow(-1, i+1);

        if(seq[i]>(k*seq[i-1])){
            count[i]=count[i-1]+1;
        }
    }

    int max=1;
    for(int i=0;i<len;i++)
        if(count[i]>max)
            max=count[i];

    return max;
}

---

Explanation:

Corresponding to every element, I have a count element that represents the continuous alternate sequence up to that point.

seq:    1, 7, 4, 9, 2, 5
count:  1, 1, 1, 1, 1, 1

i=1 7 > 1    count[1]= count[0]+1 = 2
i=2 4 > -7   count[2]= count[1]+1 = 3
i=1 9 > 4    count[3]= count[2]+1 = 4
i=1 2 > -9   count[4]= count[3]+1 = 5
i=1 5 > 2    count[5]= count[4]+1 = 6

After that I am simply printing the max of the count array.

---

Error:

The above works correctly for

{ 1, 7, 4, 9, 2, 5 }                     ->  6
{ 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 }   ->  7

However, it gives wrong results for

{ 1, 2, 3, 4, 5, 6, 7, 8, 9 } gives 9 but should be 2.
{ 70, 55, 13, 2, 99, 2, 80, 80, 80, 80, 100, 19, 7, 5, 
  5, 5, 1000, 32, 32 } gives 2 but should be 8.

Answer 1

I'm not sure how answerable this is . . . your approach is really completely wrong. :-/

To see this, consider the following: your calculation for each element of count depends only on the single previous element of count, and your running calculation for max depends only on the current element of count. That means that you don't even need the count array: your whole algorithm could be translated into a single pass requiring O(1) space. But, as a "test-taker", you know that this problem can't (easily) be solved in a single pass with O(1) space, because if it could, you wouldn't have been instructed to use dynamic programming.

The core reason that your algorithm is wrong is that you only ever compare each element of seq to its immediate predecessor, but subsequences are allowed to (and usually do) "jump over" intermediate values.

One confounding factor, which is responsible for some of the more confusing aspects of your output, is that the seq[i]>(k*seq[i-1]) check doesn't mean what I think you think it means. You probably wanted something closer to k*(seq[i]-seq[i-1])>0 — but even that will give quite wrong results. You really just need to scrap this algorithm and write a new one.