注意二分查找。
1
#include<iostream>2
#include<string.h>3
#define LEN 400104
using namespace std;5
int len;6
int L[LEN];7
int A[LEN];8
int binSearch(int bg, int ed, int n)9


{10
int mid;11
while(bg <= ed)12

{13
mid = (bg + ed) / 2;14
if(n > L[mid] && n < L[mid + 1])15
return mid + 1;16
else if(n > L[mid])17
bg = mid + 1;18
else19
ed = mid - 1;20
}21
}22
int main()23


{24
int i, j;25
int n, p;26
cin >> n;27
while(n--)28

{29
cin >> p;30
for(i = 0; i < p; i++)31
cin >> A[i];32
L[0] = 0;33
L[1] = A[0];34
len = 1;35
for(i = 1; i < p; i++)36

{37
if(A[i] > L[len])38
L[++len] = A[i];39
else if(A[i] < L[1])40
L[1] = A[i];41
else42

{43
int mid = binSearch(1, len, A[i]);44
L[mid] = A[i];45
}46
}47
cout << len << endl;48
}49
//system("pause");50
return 0;51
}52


