Time limit: 1000 ms memory limit: 65536 KB
Submit number: 195 by counting: 100
[title description]
Criminal kidd is a legendary criminal, specifically aimed at jewelry super thief, and he is the most prominent place, is that he always escape nakamura police department of containment, which is largely thanks to his carry-on is advantageous for the operation of gliding,
Jason kidd as usual, one day, the criminal stole a precious diamond, only to be conan children got wise to disguise, and his gliding of the power plant was destroyed by conan play football, you have to escaped criminal kidd can only operate the damaged gliding,
Assumes that the city a total of N buildings arranged in a line, each building height of each are not identical, the initial, criminal kidd can be in any of the top of the building, he can choose a direction to escape, but not the way to change direction (as well in the process behind chasing), because the gliding power unit is damaged, he can only glide down (i.e., only from higher glide to lower buildings), he wants as much as possible through different at the top of the building, so that we can reduce the impact of the fall, to reduce the possibility of injury, excuse me, he can be at most how many different building at the top of the (including initial construction)?
[enter]
Input data to the first line is an integer K (K<100), on behalf of the K group test data,
Each set of test data contains two lines: the first line is an integer N (N<100), on behalf of the N building, the second line contains N different integers, each corresponding to a building height h (0 & lt; H<10000), according to the order of the construction, the given
[output]
For each set of test data, output a line contains an integer, kidd can most represent criminal after a number of buildings,
[input sample]
3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
1 2 3 4 5 6 7 8 9 10
[output sample]
6
6
9
The problem on the surface is the largest rise in subsequence and largest decline in the subsequence maximize,
But if the data is that?
1, 3, 4, 9
To understand as subject, gliding if there are any tall buildings in the process, will be blocked and cannot continue to glide, so when the maximum climbing subsequence of 1, 3, 4, among 9 blocked, however, can only go 1, 3, 4, and
Program at this time how to change??????
Big help!!!!!!
CodePudding user response:
Algorithm, temporarily haven't, can only help,