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; }