HDU 1950 Bridging signals

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int maxn = 40000 + 10;
 8 int a[maxn];
 9 int dp[maxn];
10 
11 int main(void)
12 {
13     #ifdef LOCAL
14         freopen("1950in.txt", "r", stdin);
15     #endif
16 
17     int N;
18     scanf("%d", &N);
19     while(N--)
20     {
21         int n;
22         scanf("%d", &n);
23         int i;
24         for(i = 1; i <= n; ++i)
25             scanf("%d", &a[i]);
26         dp[1] = a[1];
27         int len = 1;
28 
29         for(i = 2; i <= n; ++i)
30         {
31             int left = 1;
32             int right = len;
33             while(left <= right)
34             {
35                 int mid = (left + right) >> 1;
36                 if(dp[mid] < a[i])
37                     left = mid + 1;
38                 else
39                     right = mid - 1;
40             }
41             dp[left] = a[i];
42             if(left > len)
43                 ++len;
44         }
45         printf("%d\n", len);
46     }
47     return 0;
48 }