Zig Zag Subsequence

We can find every length of the zig-zag arrangement and find the maximum length out of it.

We will use a recursive function, Solve (tokenArray, index, isIncreasing) which will take the array “tokenArray”, index “index”, and a Boolean variable “isIncreasing” which will tell us whether we need to find increasing “Zig-Zag” arrangement or decreasing “Zig-Zag” arrangement. 

If the function “Solve” is called after decreasing “Zig-Zag” arrangement then we will call the same function with increasing “Zig-Zag” arrangement and Vice-Versa.

Algorithm –

• Create a recursive “Solve” function:
• Initialise a variable “maxCounter” = 0, which will store the maximum increasing or decreasing arrangement.
• Now iterate over the “tokenArray” from index ‘i’ = “index” + 1 to the length of the “tokenArray”.
• Inside the iteration, if “isIncreasing” is true and the current iterative element of array is greater than the “index” element of the array OR if “isIncreasing” is false and the current iterative element of the array is smaller than the “index” element of the array then:
• Store the maximum count in the “maxCounter” by calling the “Solve” function recursively for the rest elements and making the Boolean operator “isIncreasing” as False.
• maxCounter = 1 + max (maxCounter, Solve (tokenArray, i, !isInc))
• Return the “maxCounter”. 
• Inside the main “ZigZagSubsequence” function:
  • If the length of the “arr” is less than 2 then we will be returning with the length of “tokenArray”.
  • If the length of “arr” is greater than 2 then we will be returning with maximum count of “Zig-Zag” arrangement by calling recursive function “Solve” first by making Boolean operator “isIncreasing” as True and then by making “isIncreasing” as False
    • maxCounter = 1 + max (Solve (tokenArray, 0, true), Solve (tokenArray,0, false)).

In this approach, we will take a DP matrix of size (N+1 * 2) where ‘N’ is the size of the tokenArray. This DP matrix will store the count of maximum “Zig-Zag” subsequences for increasing (“isIncreasing” = 1) as well as for the decreasing arrangement (“isIncreasing” = 0).

DP [ i ][ 0 ] will store maximum count of subsequence for increasing arrangement and DP [ i ][ 1 ] will store the maximum count of subsequence for decreasing arrangement.

Algorithm –

• Inside the recursive “Solve” function:
• Initialise DP matrix with values equal to ‘-1’ .
• If the passed “index” is greater than the size of the “tokenArray” then return 0.
• If the value of DP matrix is not equal to ‘-1’ 
  • Return with the value which means we have already filled the maximum length of the “Zig-Zag” subsequence.
• If “isIncreasing” is equal to 1 (i.e. last element is in increasing arrangement) then:
• Check for the next element of “tokenArray” to be smaller than the current “index” element
• Update the DP matrix with the count of “Zig-Zag” subsequence by calling the “Solve” function recursively.

DP [ index ][ isIncreasing ] = 1 + solve(tokenArray, index+1, 1 - isIncreasing, DP)

• If the next element is not smaller than the current “index” element, then update the current element recursively and store the value in the DP matrix:
  • DP [ index ][ isIncreasing ] = solve(tokenArray, index+1, isIncreasing, DP)
• Similarly do check for “isIncreasing” = 0 (i.e last element is in decreasing arrangement) and then check if next element is increasing. Then update the DP matrix accordingly.
• Return the DP [ index ][ isIncreasing ].
• Inside the main “ZigZagSubsequence” function:
• Store the length of maximum length of “Zig-Zag” subsequence considering first element is of decreasing arrangement in:

DP [ 0 ][ 0 ] = Solve (tokenArray, 0, 0, DP)

• Store the length of maximum length of “Zig-Zag” subsequence considering first element is of increasing arrangement in:

DP [ 0 ][ 1 ] = Solve (tokenArray, 0, 1, DP)

• Now, return maximum from DP [ 0 ][ 1 ] and DP [ 0 ][ 1 ].

To understand this approach, we will take two arrays for dp named “Dp1” and “Dp2”. 

Whenever we pick up any element of the array to be a part of the “Zig-Zag” subsequence, that element could be a part of an increasing “Zig-Zag” arrangement or a decreasing “Zig-Zag” depending upon the previous element.

“Dp1[ i ]” refers to the length of the longest “Zig-Zag” subsequence obtained so far considering “ith” element as the last element of the “Zig-Zag” subsequence and ending with an increasing “Zig-Zag”.

Similarly, “Dp2[ i ]” refers to the length of the longest “Zig-Zag” subsequence obtained so far considering “ith” element as the last element of the “Zig-Zag” subsequence and ending with a decreasing “Zig-Zag”.

“Dp1[ i ]” will be updated every time we find an increasing “Zig-Zag” ending with the “ith” element. Now, to find “Dp1[ i ]” we need to consider the maximum out of all the previous “Zig-Zag” sub sequences ending with a decreasing “Zig-Zag” that is “Dp1[ j ]”, for every j < i and tokenArray [ j ] < tokenArray [ i ]. 

 

Similarly, “Dp2[ i ]” will be updated.

 

Our answer will be stored on the (N – 1)th index (where N will be the length of the “tokenArray”) of the dp arrays in such a way that maximum of “Dp1[N-1]” and “Dp2[N-1]” + 1 will be giving us the maximum length of the “Zig-Zag” subsequence.

 

This approach will have time complexity of O(N ^ 2) and O(N ^ 2 ) as space complexity.

 

We can further optimise this approach to constant space complexity and linear time complexity:

 

• Optimised Approach

 

Since we are dealing with only the current and the previous element of “tokenArray” in the above approach, so instead of taking 2 dp arrays we can make it possible with two variables “increasingElement” and “decreasingElement” which will store the last elements of “tokenArray”.

Algorithm –

• Initialise “increasingElement” = 1 and “decreasingElement” = 1
• If ( tokenArrray [ i ] > tokenArray [ i – 1 ]) then update the “increasingElement” as
  • increasingElement = decreasingElement + 1
• Otherwise if ( tokenArray [ i ] > tokenArray [ i – 1 ] ) then update the “decreasingElement” as
  • decreasingElement = increasingElement + 1
• Return the maximum of “increasingElement” and “decreasingElement”.

This problem is equivalent to finding number of alternating maximum and minimum peaks in the “tokenArrray”. If we consider choosing any intermediate number to be a part of the “Zig-Zag” subsequence, the maximum length of “Zig-Zag” subsequence will always be less than or equal to the one obtained by choosing only consecutive maximum and minimum elements.

Zig - Zag subsequence choosing ‘D’ as 3rd point : “A B D E F G”

Zig – Zag subsequence choosing ‘C’ as 3rd point: “A B C G”

From the figure, we can see that, if we choose ‘C’ as a 2nd point in the “Zig-Zag '' subsequence, we can’t include point ‘E’ and ‘F’. Thus we won't be able to obtain the maximum subsequence length.

Algorithm –

• We will take two variables “differenceBefore” which will be indicating whether current number lies in increasing or decreasing “Zig-Zag” arrangement.
• If “differenceBefore” > 0, it indicates that we are in increasing “Zig-Zag” arrangement and if “differenceBefore” < 0, it indicates that we are in decreasing “Zig-Zag” arrangement.
• We will update the length of the subsequence when ( tokenArray [ i ] – tokenArray [ i – 1 ] ) < 0.
• Similarly, if “differenceBefore” < 0, We will update the length of the subsequence when ( tokenArray [ i ] – tokenArray [ i – 1 ] ) > 0