Programming Logic – You have been given an array and you have to find the length of the maximum zigzag subsequence…


You have been given an array and you have to find the length of the maximum zigzag subsequence. A Zig-Zag subsequence is a subsequence such that the elements are alternatingly increasing and decreasing.

You have been given the following pseudocode for finding the maximum length of zigzag sequence in a given array.

get the input in an array named arr
initialise the a 2d array named Z[length of array][2]
for base case make all entries as 1

/* Note:
Z[i][0] = Length of the longest Zig-Zag subsequence ending at index i and last element is greater than its previous element
Z[i][1] = Length of the longest Zig-Zag subsequence ending at index i and last element is smaller than its previous element */

loop 1: for i = 1 to length of array
loop 2: for j = 0 to i
if (X)
Z[i][0] = Z[j][1] + 1
if( arr[j] > arr[i] && Z[i][1] < Z[j][0] + 1)
Y

find max of all entries and return the value

What can be used in place of X and Y to complete the pseudocode given above?

Related Posts

Close Bitnami banner
Bitnami