Longest alternating subsequence
Given a sequence of numbers you have to find out the longest alternating subsequence and print the length of the subsequence. A sequence is an alternating sequence when it will be maintain like (increasing) -> (decreasing) -> (increasing) -> (decreasing) or (decreasing) -> (increasing) -> (decreasing) -> (increasing).
Input:
T Test case
T no. of input array along with their element no. N
E.g.
3
8
2 3 4 8 2 5 6 8
8
2 3 4 8 2 6 5 4
7
6 5 9 2 10 77 5
Constrain:
1≤ T ≤ 20
1≤ N ≤50
1≤ A[i] ≤50
Output:
Print the length of the longest alternating subsequence.
Example
T=3
Input:
8
2 3 4 8 2 5 6 8
Output:
4 (4, 8, 2, 5)
Input:
8
2 3 4 8 2 6 5 4
Output:
5 ( 4, 8, 2, 6, 4 )
Input:
7
6 5 9 2 10 77 5
Output:
6 (6, 5, 9, 2, 10, 5 )