果的LIS，直接贴代码
#include <stdio.h>
int a[40000], b[40000], n, i, j, sum;
void LIS()
{
int left= 0, right= sum-1, mid;
if(0 == i)
{
b[0]=a[i];
}
else
{
while(left <= right)
{
mid= (left + right)>>1;
if(b[mid] > a[i])
{
right= mid-1;
}
else
{
left= mid+1;
}
}
b[left]= a[i];
if(left >= sum)
{
sum++;
}
}
}
int main ()
{
int m, j;
scanf("%d", &m);
for(j= 0; j < m; j++)
{
scanf("%d", &n);
sum= 1;
for(i= 0; i < n; i++)
{
scanf("%d", a+i);
LIS();
}
printf("%d\n", sum);
}
return 0;
}