http://poj.org/problem?id=3903
这个题目是一个求最长递增子序列，这个只是求长度而已，所以可以用LIS
所谓的LIS也就是用二分优化来减少时间而已，而且其只能求出最长的序列，但其所包含的并不是最长的序列
#include <iostream>
#include <stdio.h> using namespace std; int a[],dp[]; int main()
{
int n;
while(scanf("%d",&n)>)
{
for(int i=;i<n;i++)
scanf("%d",&a[i]);
dp[]=a[];
int len=;
for(int i=;i<n;i++)
{
int left=,right=len-,mid;
if(a[i]>dp[len-])
dp[len++]=a[i];
else{
right=len-;
while(left<=right)
{ mid=(left+right)/;
if(dp[mid]<a[i]) left=mid+;
else right=mid-;
}
dp[left]=a[i];
}
}
printf("%d\n",len);
}
return ;
}