k217. 11240 - Antimonotonicity - 高中生程式解題系統

Content

我有一個長度為 n 的 Fred 序列，由 1 到 n 之間的整數組成。Fred 序列的元素皆不相同。

我想找到一個盡可能長的 Fred 的子序列 Mary 並具有以下屬性：

Mary[0] > Mary[1] < Mary[2] > Mary[3] < ...

Input

第一行包含一個整數 T (T <= 50)

接下來 T 行，每行的一個數字為 n (n <= 30000)，代表接下來有 n 個數字

接下來 n 個數字，代表一個 Fred 序列

Output

對於每個 Fred 序列，輸出最長子序列 Mary 的長度

Sample Input #1

4
5 1 2 3 4 5
5 5 4 3 2 1
5 5 1 4 2 3
5 2 4 1 3 5

Sample Output #1

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (50%): 1.0s , <1M
公開測資點#1 (50%): 1.0s , <1M

Hint ：

Tags:

出處:

UVA [管理者： ig99lp33lp33 (위즈원) ]