时间复杂度为〇(nlogn)的算法，下面就来看看。
我们再举一个例子：有以下序列A[]=3 1 2 6 4 5 10 7，求LIS长度。
我们定义一个B[i]来储存可能的排序序列，len为LIS长度。我们依次把A[i]有序地放进B[i]里。（为了方便，i的范围就从1~n表示第i个数）
A[1]=3，把3放进B[1]，此时B[1]=3，此时len=1，最小末尾是3
A[2]=1，因为1比3小，所以可以把B[1]中的3替换为1，此时B[1]=1，此时len=1，最小末尾是1
A[3]=2，2大于1，就把2放进B[2]=2，此时B[]={1,2}，len=2
同理，A[4]=6，把6放进B[3]=6，B[]={1,2,6}，len=3
A[5]=4，4在2和6之间，比6小，可以把B[3]替换为4，B[]={1,2,4}，len=3
A[6]=5，B[4]=5，B[]={1,2,4,5}，len=4
A[7]=10，B[5]=10，B[]={1,2,4,5,10}，len=5
A[8]=7，7在5和10之间，比10小，可以把B[5]替换为7，B[]={1,2,4,5,7}，len=5
最终我们得出LIS长度为5。但是，但是！！这里的1 2 4 5 7很明显并不是正确的最长上升子序列。是的，B序列并不表示最长上升子序列，它只表示相应最长子序列长度的排好序的最小序列。这有什么用呢？我们最后一步7替换10并没有增加最长子序列的长度，而这一步的意义，在于记录最小序列，代表了一种“最可能性”。假如后面还有两个数据8和9，那么B[6]将更新为8，B[7]将更新为9，len就变为7
lower_bound(a,a+n,i)函数 返回从数组a到a+n中第一个>=i的元素地址
upper_bound(a,a+n,i)函数 返回从数组a到a+n中第一个>i的元素地址
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=;
int a[MAXN];
int d[MAXN];
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
d[]=a[];
int len=;
for(int i=;i<=n;i++)
{
if(a[i]>d[len])
d[++len]=a[i];
else
{
int j=lower_bound(d+,d+len+,a[i])-d;
d[j]=a[i];
}
}
printf("%d\n",len);
return ;
}