Longest Zigzag Subsequence

Longest zigzag subsequence

In this post, we will discussing another problem called longest zigzag subsequence which can be solved using dynamic programming.

A sequence of numbers is called a zigzag sequence if differences between successive numbers strictly alternate between positive and negative value. In other words, zigzag subsequence is where elements of subsequence are alternate increasing and decreasing order, means, they satisfy below conditions:

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

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

For example, 1,9,3,9,1,6 is a zigzag 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 zigzag sequences, first sequence is not because its first two differences are positive and second because its last difference is zero.
Coming to the problem of the day : Given an array of integers, find longest zigzag subsequence.
For example, answer for array below is 5 as shown

Longest zigzag subsequence

We have already seen a similar problem called find longest increasing subsequence in array. That problem is solve using dynamic programming approach. To apply dynamic programming, we need to properties : first, Optimal subproblem structure, that is solution of original problem depends on optimal solution of subproblem; and second, overlapping subproblems, so that we can save computation by memoization.

Do these two properties exist in this problem? Does longest zigzag subsequence till length i has anything to do with longest zigzag subsequence till j where j is less than i? Also, it is already clear that zigzag can start with decreasing first and then increasing or increasing first and then decreasing.

To add ith as next element in subsequence, consider two cases. First, ith element can be greater than previous element in longest zigzag subsequence till j where j < i. In this case, we are looking for all such j where A[j] < A[i]. Another criteria for j should be that A[j] less than previous element in sequence, that means, at j, we are looking exactly opposite condition than that i.

Second, ith element can be less than previous element in longest zigzag subsequence till j where j < i. In this case, we are looking for all such j where A[j] > A[i]. Another criteria for j should be that A[j] is greater than previous element in sequence, that means, at j again, we are looking exactly opposite condition than that at i.
For each i store this two cases.

Let’s say increase[i] describes LZS, for the first case and decrease[i] describes it for the second case.

  increase[i] = max(decrease[j] + 1) for all j< i && A[j] < A[i]
  decrease[i] = max(increase[j] + 1) for all j< i && A[j] > A[i]

Longest zigzag subsequence dynamic programming approach

Before going through the implementation, it will be great if you can go through Longest increasing subsequence using dynamic programming
Implementation wise, both increase and decrease array can be one two dimensional array Table[][]. Table[i][0] represents length of longest zigzag subsequence ending at i with A[i] being greater than A[j] for all j in earlier subsequences.

Similarly, Table[i][1] represents length of subsequence ending at i with A[i] being less than A[j] for all j in earlier subsequences.

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

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

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

Longest zigzag subsequence Implementation

#include <stdio.h>
#include <stdlib.h>
 
int max(int a, int b) {  return (a > b) ? a : b; }
 
int longestZigzagSubsequence(int A[], int n)
{
    int Table[n][2];
 
    for (int i=0; i<n; i++){
    	Table[i][0] = 1; 
    	Table[i][1] = 1;
    }
 
    int result = 1;
 
    for (int i=1; i<n; i++) {
        for (int j=0; j<i; j++){
        	// If A[i] is greater than last element in subsequence, 
        	//then check with Table[j][1]
        	if (A[j] < A[i] && Table[i][0] < Table[j][1] + 1)
                    Table[i][0] = Table[j][1] + 1;
                /* If A[i] is smaller than last element in subsequence,
                then check with Table[j][0] */
                if( A[j] > A[i] && Table[i][1] < Table[j][0] + 1)
                   Table[i][1] = Table[j][0] + 1;
        }
 
        /* Pick maximum of both values at index i  */
        if (result < max(Table[i][0], Table[i][1]))
            result = max(Table[i][0], Table[i][1]);
        printf("\n %d", result);
    }
 
    return result;
}

int main(void) {
	int A[] = { 1,7,4,9,2,5 };
	int size = sizeof(A)/sizeof(A[0]);
	printf("\n Length of longest zigzag subsequence : %d", longestZigzagSubsequence(A,size));
	return 0;
}

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.