Longest zigzag subsequence of sequence | Dynamic Programming Set 2

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.

Algorithm Paradigm : Dynamic Programming

mls[i,0] represents maximum length subsequence ending at i such that the difference between the last two elements is positive.
mls[i,1] represents maximum length subsequence ending at i such that the difference between the last two elements is negative.

after generating these two array take maximum value from these two array.

Algo:

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

Time complexity: O(n2)


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   2   2   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

 

#include<iostream>
#include<climits>
using namespace std;

int GetMaxZigZagSubsequence(int arr[],int n)
{
   int iMax = INT_MIN;
   int **mls = new int*[n];
   for(int i = 0 ;i<n;i++)
   {
       mls[i] = new int[2];
   }
   for(int i = 0;i<n;i++)
   {
       mls[i][0] = mls[i][1] = 1;
       for(int j = 0; j < i;j++)
       {
           if(arr[i] > arr[j])
           {
               mls[i][0] = std::max(mls[j][1]+1,mls[i][0]);
           }
           else if(arr[i] < arr[j])
           {
               mls[i][1] = std::max(mls[j][0]+1,mls[i][1]);
           }
       }
   }
   for(int i = 0; i<n; i++)
   {
       if(iMax < mls[i][0])
       {
           iMax = mls[i][0];
       }
       if(iMax < mls[i][1])
       {
           iMax = mls[i][1];
       }
   }
   //delete mls[][] array
   for(int i = 0;i<n;i++)
   {
       int* a = mls[i];
       delete [] a;
   }
   delete [] mls;
   return iMax;
}

int main( )
{
   int arr[] = {1,7,5,10,13,15,10,5,16,8};
   int iMaxSubsequence = GetMaxZigZagSubsequence(arr,sizeof(arr)/sizeof(int));
   cout<<"Ans = "<<iMaxSubsequence<<endl;

   int arr1[] = { 1, 7, 4, 9, 2, 5 };
   iMaxSubsequence = GetMaxZigZagSubsequence(arr1,sizeof(arr1)/sizeof(int));
   cout<<"Ans = "<<iMaxSubsequence<<endl;

   int arr2[] = { 44 };
   iMaxSubsequence = GetMaxZigZagSubsequence(arr2,sizeof(arr2)/sizeof(int));
   cout<<"Ans = "<<iMaxSubsequence<<endl;

   int arr3[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
   iMaxSubsequence = GetMaxZigZagSubsequence(arr3,sizeof(arr3)/sizeof(int));
   cout<<"Ans = "<<iMaxSubsequence<<endl;

   int arr4[] = { 374, 40, 854, 203, 203, 156, 362, 279, 812, 955,
       600, 947, 978, 46, 100, 953, 670, 862, 568, 188,
       67, 669, 810, 704, 52, 861, 49, 640, 370, 908,
       477, 245, 413, 109, 659, 401, 483, 308, 609, 120,
       249, 22, 176, 279, 23, 22, 617, 462, 459, 244 };
   iMaxSubsequence = GetMaxZigZagSubsequence(arr4,sizeof(arr4)/sizeof(int));
   cout<<"Ans = "<<iMaxSubsequence<<endl;
   return 0;
}

Site Footer