Given an array A of N positive integers. The task is to find the longest Zig-Zag subsequence problem such that all elements of this are alternating (Ai-1 < Ai > Ai+1).
Input:
The first line of input contains an integer T denoting the number of test cases. Each test case contains an integer N which denotes the number of elements in the array A. Next line contains space separated n elements in the array A.
Output:
Print the length of the longest such subsequence.
Constraints:
1 <= T <= 200
1 <= N <= 103
1 <= Ai <= 105
Example:
Input:
2
6
5 5 10 100 10 5
3
1 2 3
Output:
3
2
Explanation:
Testcase 1: 5, 10, 5 is the longest common subsequence with elements alternating.
https://practice.geeksforgeeks.org/problems/longest-zig-zag-sub-sequence/0
Given an array A of N positive integers. The task is to find the longest Zig-Zag subsequence problem such that all elements of this are alternating (Ai-1 < Ai > Ai+1).
Input: The first line of input contains an integer T denoting the number of test cases. Each test case contains an integer N which denotes the number of elements in the array A. Next line contains space separated n elements in the array A.
Output: Print the length of the longest such subsequence.
Constraints: 1 <= T <= 200 1 <= N <= 103 1 <= Ai <= 105
Example: Input: 2 6 5 5 10 100 10 5 3 1 2 3
Output: 3 2
Explanation: Testcase 1: 5, 10, 5 is the longest common subsequence with elements alternating.