Problem title
Difficulty
Avg time to solve

Sort Array Of Strings
Easy
15 mins
Ninja And His Old Friends
Easy
15 mins
Ninja And XOR
Easy
20 mins
Magnet Array Problem
Easy
15 mins
Best Line
Easy
20 mins
Longest sub-array with positive product
Easy
15 mins
Rank from Stream
Moderate
15 mins
First Repeated Character
Moderate
30 mins
Longest Alternating Subsequence
Moderate
15 mins
Count Subarrays Having Product Less Than K
Moderate
25 mins 3

# Longest Alternating Subsequence

Difficulty: MEDIUM
Avg. time to solve
15 min
Success Rate
85%

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.
``````
##### 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.
``````   Console