Longest Alternating Subsequence

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
8 upvotes
Asked in companies
DirectiAmazonBarclays

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
7
1 2 5 3 10 15 12
4 
1 4 2 3
Sample Output 1 :
5
4
Explanation of Sample Output 1:
In test case 1, Given 'ARR' = {1,2,5,3,10,15,12}, we can see that the longest alternating subsequence for this array can be {1,5,3,15,12} or {2,5,3,15,12}. Therefore, the length will be 5.

In test case 2, Given 'ARR' = {1,4,2,3} we can see that the longest alternating subsequence for this array will be {1,4,2,3}. Therefore, length will be 4.
Sample Input 2 :
2
5
1 2 3 4 5      
3
1 3 2
Sample Output 2 :
2
3
Explanation of Sample Output 2:
In test case 1, Given 'ARR' = {1,2,3,4,5}, we can see that the longest alternating subsequence for this array can be any pair of two elements. Therefore, the length will be 2.

In test case 2, Given 'ARR' = {1,3,2} we can see that the longest alternating subsequence for this array will be {1,3,2}. Therefore, the length will be 3.
Hint

Can you do it recursively?

Approaches (4)
Recursive

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.

Time Complexity

O(N ^ N), where ‘N’ denotes the length of the array.

 

Since we are making recursive calls in a loop of length ‘N’ and for every element, ‘N’ recursive calls would be made. Therefore, the net time complexity will be O(N ^ N).

Space Complexity

O(N ^ 2), where ‘N’ denotes the length of the array.

 

Space complexity will be the product of the height of the recursive call tree and the space used in one call. Means, O(Height) * O(space in one call). Thus, the final space complexity will be O(N) [ Height of the recursion tree ] * O(N) [ Space used in a call ] = O(N ^ 2). 

Code Solution
(100% EXP penalty)
Longest Alternating Subsequence
Full screen
Console