Longest alternating Subsequence

Tags: ,

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

A sequence of numbers is called a alternating sequence if differences between successive numbers strictly alternate between positive and negative value. In other words, alternate 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 alternating subsequence.

We have already seen a similar problem longest increasing subsequence in an array. That problem is solved using a dynamic programming approach. To apply dynamic programming, we need to properties: first, Optimal subproblem structure, that is the solution of the original problem depends on the 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 the longest zigzag subsequence till length i has anything to do with the longest zigzag subsequence till j where j is less than i? Also, it is already clear that alternating subsequence 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 criterion for j should be that A[j] less than the previous element in the 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 criterion for j should be that A[j] is greater than the previous element in the sequence, that means, at j again, we are looking exactly opposite condition than that at i.
For each i we will store these two.

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 alternating 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))

Click here to see longest alternating 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;
}
Complexity of dynamic programming approach to find longest alternate 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.