Walls of the North
Practice
3.8 (51 votes)
Ready
Segment trees
Dynamic programming
Medium
Problem
73% Success 608 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

"You know nothing, Jon Snow."

Jon and Ygritte have fallen in love with each other and have forgotten that they have a lot of important things to do. While crossing the walls of the North (imagine that there can be more than just one such wall), they have decided to play the following game:

There are N walls. Ygritte tells Snow the actual height of each wall and challenges him to choose a subsequence of the walls to cross, such that heights of chosen walls form an alternating sequence. In more detail, he has to choose a subsequence A[1..k] of heights of all the walls, such that for all i = 1, 2,...k-2 either A[i] >= A[i + 1] <= A[i + 2] or A[i] <= A[i + 1] >= A[i + 2]. In order to make the game more challenging, she wants him to choose the longest such subsequence from all possible ones.

Snow is not only an exceptional warrior, but also a good mathematician, so he quickly told Ygritte the correct answer and that earned a a kiss from her! Can you try to match his problem solving skills and provide the length of the subsequence he has chosen?

Input format

In the first line, there is a single integer T denoting the number of test cases to handle. Then descriptions of these tests follow. Each test case is described in exactly two lines. In the first of them, there is a single integer N denoting the number of walls. In the second line, there are N space separated integers H[1], H[2], ..., H[N], where H[i] denotes the height of the ith wall.

Output format

In a single line, output the length of the sequence chosen by Snow.

Constraints

1 <= T <= 10
1 <= N <=105
1 <= H[i] <= 109

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
24 votes
Tags:
ApprovedMathMediumOpen
Points:50
11 votes
Tags:
Divide-and-conquer algorithmFast Fourier transformGenerating FunctionsMedium
Points:30
18 votes
Tags:
AlgorithmsBinary SearchMediumPrefix sumSearchingTwo pointerprefix-sum