> #include<iostream>
> #include<string.h>
> using namespace std;
> 
> int dp[100000];
> int  a[100000];
> int main()
> {
>     int n;
> 	cin>>n;
> 	while(cin>>n)
> 	{
> 		int longlist=1;
> 	    for(int i=1;i<=n;i++)
> 		{
> 		     cin>>a[i];
> 		}
> 		memset(dp,1,sizeof(dp));
> 		for(int i=2;i<=n;i++)
> 		{
> 		   for(int j=1;j<i;j++)
> 		   {
> 		        if(a[j]<a[i])
> 					dp[i]=max(dp[j]+1,dp[i]);
> 
> 		   }
> 		   longlist=max(dp[i],longlist);
> 		}
>      cout<<longlist<<endl;
> 	}
> 	return 0;
> }
数据较大，需要O(n logn)的LIS算法