Longest ZigZag Subsequence

Longest zigzag subsequence

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative.  This post is about finding longest zigzag subsequence. Another definition is , zigzag subsequence is where elements of subsequence are alternating order, means, they satisfy below conditions:

x1 < x2 > x3 < x4 > x5 < …. xn 
x1 > x2 < x3 > x4 < x5 > …. xn

A sequence with fewer than two elements is trivially a zigzag sequence.

For example, 1,9,3,9,1,6 is a zig-zag sequence because the differences (8,-6,6,-8,5) are alternately positive and negative. In contrast, 1,6,7,4,5 and 1,9,4,4,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 array of integers, find length of the longest zigzag subsequence.

Intention of this post to utilize what we learned when we solved longest increasing subsequence in array using dynamic programming. This problem was asked in top coder. If you want to see detailed problem and other examples, please refer : Zigzag problem at top coder.

Longest zigzag subsequence using dynamic programming

Let’s assume we have an array A with given integers. Table(i,0) represents the length of longest zigzag subsequence ending at i with last difference as positive, mean difference between last and second last elements of subsequence is positive.

Similarly, Table(i,1) represents length of longest zigzag subsequence ending at i with last difference being negative.

With these definitions, below relations can be worked out.

Table(i,0) = max (Table(i,0), Table(j,1) + 1); 
             for all j < i and A[j] < A[i] 
Table(i,1) = max (Table(i,1), Table(j,0) + 1); 
             for all j < i and A[j] > A[i]

How do we get it? When we are at index i of an array, this element at index i can be included in longest zigzag subsequence, then there two possibilities. First, that element at index i is greater than the last element in previous longest zigzag subsequence. In this case, we look for all j < i where A[j] < A[i] and update Table[i,0] for maximum value of Table(j,1) +1 till i for j < i.

Second, element at index i is less than last element in zigzag sequence. In this case, we look for all j < i where A[j] > A[i] and update Table(i,0) for maximum value Table(j,1) +1 till i for j< i.

What will be length of longest zigzag subsequence for index i?

Result =  max (Table(i,0), Table(i,1))

Now that we know the recursion relation, implementation is really simple.

Longest zigzag subsequence problem implementation

Complexity of dynamic programming approach to find longest zigzag subsequence is O(N2) using O(N) extra space.

Please share if there is something wrong or missing. If you want to contribute to website, please contact us.