思路：

LIS，二分。

实现：

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 int d[40010]; 5 int fuck(int x, int right) 6 { 7     int left = 0; 8     int pos = -1; 9     while (left <= right)10     {11         int middle = (left + right) / 2;12         if (d[middle] >= x)13         {14             pos = middle;15             right = middle - 1;16         }17         else18         {19             left = middle + 1;20         }21     }22     return pos;23 }24 int main()25 {26     int t, n;27     int temp;28     cin >> t;29     while (t--)30     {31         cin >> n;32         int cnt = 0;33         for (int i = 0; i < n; i++)34         {35             scanf("%d", &temp);36             if (cnt == 0 || temp > d[cnt - 1])37             {38                 d[cnt++] = temp;39             }40             else41             {42                 int pos = fuck(temp, cnt - 1);43                 d[pos] = temp;44             }45         }46         printf("%d\n", cnt);47     }48     return 0;49 }