最長(zhǎng)遞增子序列的O(nlogn)算法，用一個(gè)數(shù)組a[i]表述當(dāng)前序列長(zhǎng)度為i時(shí)末尾元素的最小值。
這樣當(dāng)輸入一個(gè)數(shù)時(shí)，如果它比a[i-1]大，就直接添加到a[i]，否則就在a[i]中進(jìn)行二分查找到該元素的位置(因?yàn)閍[i]是單調(diào)遞增的)。
另外二分的時(shí)候需要注意別陷入死循環(huán)了。
#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;
}