Longest Alternating Subsequence

Posted: 27 Feb, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given an array ‘ARR’ of integers. Your task is to find the length of the longest alternating subsequence.

Note:
A sequence a1, a2, .... an is called an alternating sequence if its elements satisfy one of the following relations : a1 < a2 > a3 < a4 > a5..... or  a1 > a2 < a3 > a4 < a5.
For example:
'ARR' = {3, 10, 1, 2, 30}, the longest alternating subsequence for this array can be {3, 10, 1, 30} or {3, 10, 2, 30}. Therefore, the answer will be 4.
Input format :
The first line of input contains an integer 'T' denoting the number of test cases.

The first line of each test case contains a single integer 'N' representing the length of the array.

The second line of each test case contains 'N' space-separated integers representing the elements of the array 'ARR'.
Output format :
For each test case, return a single integer which is the length of the longest alternating subsequence. 

Print the output of each test case in a separate line.
Note:
You don’t have to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 5000
1 <= ARR[i] <= 10^5

Where 'ARR[i]' denotes the ith element of 'ARR'.

Time limit: 1 sec
Approach 1

The idea is to use recursion. Here we have two options that the next element in the sequence should be greater or smaller than the previous element. For this, we will use the indicator to indicate the above condition. 

We will declare a function helper and inside it for every element in the array we have -

  • Declare ‘RESULT’ = ‘0’.
  • Include this number in the subsequence:
    • If the indicator is ‘1’ and the previous element is less than the current element(i.e. ‘ARR[i - 1]’ < ‘ARR[i]’), include this in the subsequence as next greater.
    • If the indicator is ‘0’ and the previous element is greater than the current element(i.e. ‘ARR[i - 1]' > ‘ARR[i]’), include this in the subsequence as next smaller.
  • Recur for the next element by changing the indicator and update the result.
  • Exclude this element and recur for the next indicator remaining the same and update result.

Call this helper function in the original function twice, one for the indicator as ‘0’ and one for the indicator as ‘1’ and return the maximum of both values.

Try Problem