Dynamic programming: Find longest subsequence that is zig zag

Question

Can anyone please help me understand the core logic behind the solution to a problem mentioned at http://www.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493

A zig zag sequence is one that alternately increases and decreases. So, 1 3 2 is zig zag, but 1 2 3 is not. Any sequence of one or two elements is zig zag. We need to find the longest zig zag subsequence in a given sequence. Subsequence means that it is not necessary for elements to be contiguous, like in the longest increasing subsequence problem. So, 1 3 5 4 2 could have 1 5 4 as a zig zag subsequence. We are interested in the longest one.

I understand that this is a dynamic programming problem and it is very similar to How to determine the longest increasing subsequence using dynamic programming?.

I think any solution will need an outer loop that iterates over sequences of different lengths, and the inner loop will have to iterate over all sequences.

We will store the longest zig zag sequence ending at index i in another array, say dpStore at index i. So, intermediate results are stored, and can later be reused. This part is common to all Dynamic programming problems. Later we find the global maximum and return it.

My solution is definitely wrong, pasting here to show what I've so far. I want to know where I went wrong.

    private int isZigzag(int[] arr)
{
    int max=0;
    int maxLength=-100;
    int[] dpStore = new int[arr.length];

    dpStore[0]=1;

    if(arr.length==1)
    {
        return 1;
    }
    else if(arr.length==2)
    {
        return 2;
    }
    else 
    {           
        for(int i=3; i<arr.length;i++)
        {
            maxLength=-100;
            for(int j=1;j<i && j+1<=arr.length; j++)
            {
                if(( arr[j]>arr[j-1] && arr[j]>arr[j+1])
                    ||(arr[j]<arr[j-1] && arr[j]<arr[j+1]))
                {
                    maxLength = Math.max(dpStore[j]+1, maxLength);
                }
            }
            dpStore[i]=maxLength;               
        }
    }
    max=-1000;
    for(int i=0;i<arr.length;i++)
    {
        max=Math.max(dpStore[i],max);
    }
    return max; 
}

Your first link requires registration to access. It would be much easier to answer if the problem description was embedded in your question. — hammar
I am sorry I didn't notice that... I'll put in a quick statement of the problem. — Abhijeet Kashnia
Do you understand how to solve the basic longest increasing subsequence (without the zigzag) as well? This is just a minor modification of that, using the same techniques to solve. — hugomg
In 1 3 5 4 2, the entire sequence is zig-zag. You don't mention how equal numbers should be treated, but excluding equal numbers, aren't all sequences that are not increasing or decreasing (these have no zig-zag subsequences either, except the trivial 1 or 2 element ones). So, is 1 1 1 increasing or decreasing? — IVlad
Well, the problem you linked to is entirely different than what you're describing. Can you please decide on which one you need help with? — IVlad

IVlad IVlad · Accepted Answer · 2011-08-02T17:00:53

This is what the problem you linked to says:

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. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

This is completely different from what you described in your post. The following solves the actual topcoder problem.

dp[i, 0] = maximum length subsequence ending at i such that the difference between the
           last two elements is positive
dp[i, 1] = same, but difference between the last two is negative

for i = 0 to n do     
   dp[i, 0] = dp[i, 1] = 1

   for j = 0 to to i - 1 do
    if a[i] - a[j] > 0
      dp[i, 0] = max(dp[j, 1] + 1, dp[i, 0])
    else if a[i] - a[j] < 0
      dp[i, 1] = max(dp[j, 0] + 1, dp[i, 1])

Example:

i        = 0  1   2  3   4   5   6   7  8   9
a        = 1  17  5  10  13  15  10  5  16  8 
dp[i, 0] = 1  2   2  4   4   4   4   2  6   6    
dp[i, 1] = 1  1   3  3   3   3   5   5  3   7
           ^  ^   ^  ^
           |  |   |  -- gives us the sequence {1, 17, 5, 10}
           |  |   -- dp[2, 1] = dp[1, 0] + 1 because 5 - 17 < 0.
           |  ---- dp[1, 0] = max(dp[0, 1] + 1, 1) = 2 because 17 - 1 > 0
     1 element
   nothing to do
 the subsequence giving 7 is 1, 17, 5, 10, 5, 16, 8, hope I didn't make any careless
 mistakes in computing the other values)

Then just take the max of both dp arrays.

Dynamic programming: Find longest subsequence that is zig zag

11 Answers