最長遞增子序列的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;
}