Given a number sequence a0, a1, a2... aN-1.
If we delete some (or none) of the numbers and merge the rest in original
order, we can obtain another sequence that is a "subsequence" of the original
one.
Further more, if the numbers in the obtained subsequence is in strictly increasing
order (i.e. for each consecutive pair in subsequence, the latter is larger than the former number), then the obtained sequence is called an "increasing subsequence".
Now, given the original sequence, please find the length of LIS - "lognest inceasing
subsequence". That is, an "increasing subsequence" with maximum length that
could be obtained from the given sequence.
Input contains multiple testcases. The first line is an integer T indicating the number of testcases.
Each testcase starts with a number N denoting the length of the sequence. Then follows N numbers describing the sequence.
T <= 100
N <= 1000
0 <= ai <= 100000000
For each testcase, output a single number in a line describing the length of LIS.
4 5 1 2 3 4 5 5 5 4 3 2 1 5 5 5 5 5 5 5 1 5 2 4 3
5 1 1 3
Migrated from old NTUJ.
kelvin
| No. | Testdata Range | Score |
|---|