最长递增子序列的O(nlogn)算法，用一个数组a[i]表述当前序列长度为i时末尾元素的最小值。
这样当输入一个数时，如果它比a[i-1]大，就直接添加到a[i]，否则就在a[i]中进行二分查找到该元素的位置(因为a[i]是单调递增的)。
另外二分的时候需要注意别陷入死循环了。
#include <stdio.h>
#include <string.h>
#define N 40005
int a[N];
int main()
{
int t, tt, n, l;
scanf("%d\n", &t);
while(t--)
{
scanf("%d", &n);
scanf("%d", &tt);
memset(a, 0, sizeof(a));
a[0] = tt;
l = 1;
for(int i = 1; i < n; i++)
{
scanf("%d", &tt);
if(a[l - 1] < tt) a[l++] = tt;
else
{
int left = 0, right = l - 1, mid = (left + right) >> 1;
while(left < right)
{
if(a[mid] < tt) left = mid + 1;
else if (a[mid] > tt) right = mid;
mid = (left + right) >> 1;
}
a[mid] = tt;
}
}
printf("%d\n", l);
}
return 0;
}