O(NlgN）算法
假设存在一个序列d[1..9]={2，1，5，3，6，4，8，9，7}，可以看出来它的LIS长度为5。
下面一步一步试着找出它。
我们定义一个序列B，然后令i=1to9逐个考察这个序列。
此外，我们用一个变量Len来记录现在最长算到多少了
首先，把d[1]有序地放到B里，令B[1]=2，就是说当只有1一个数字2的时候，长度为1的LIS的最小末尾是2。这时Len=1
然后，把d[2]有序地放到B里，令B[1]=1，就是说长度为1的LIS的最小末尾是1，d[1]=2已经没用了，很容易理解吧。这时Len=1
接着，d[3]=5，d[3]>B[1]，所以令B[1+1]=B[2]=d[3]=5，就是说长度为2的LIS的最小末尾是5，很容易理解吧。这时候B[1..2]=1,5，Len＝2
再来，d[4]=3，它正好加在1,5之间，放在1的位置显然不合适，因为1小于3，长度为1的LIS最小末尾应该是1，这样很容易推知，长度为2的LIS最小末尾是3，于是可以把5淘汰掉，这时候B[1..2]=1,3，Len=2
继续，d[5]=6，它在3后面，因为B[2]=3,而6在3后面，于是很容易可以推知B[3]=6,这时B[1..3]=1,3,6，还是很容易理解吧？Len=3了噢。
第6个,d[6]=4，你看它在3和6之间，于是我们就可以把6替换掉，得到B[3]=4。B[1..3]=1,3,4，Len继续等于3
第7个,d[7]=8，它很大，比4大，嗯。于是B[4]=8。Len变成4了
第8个,d[8]=9，得到B[5]=9，嗯。Len继续增大，到5了。
最后一个,d[9]=7，它在B[3]=4和B[4]=8之间，所以我们知道，最新的B[4]=7，B[1..5]=1,3,4,7,9，Len=5。
于是我们知道了LIS的长度为5。 原文出处：原文链接
/*******************最长单调递增子序列**********************/#include<stdio.h>#define M 9void INIT_MAP(int L[]){for(int i=0;i<M;i++){scanf("%d",&L[i]);}}void procs(const int L[],int B[],int &len){int flag=0;for(int i=1;i<M;i++){printf("执行第%d次\n",i);flag=0;for(int j=0;j<=len;j++){if(L[i]<=B[j]){B[j]=L[i];flag=1;break;}}if(flag==0){B[len+1]=L[i];len++;}}}void SHOW(const int array[]){for(int i=0;i<M;i++){printf("%d ",array[i]);}printf("\n");}void main(){int L[M];INIT_MAP(L);int B[M]={0};B[0]=L[0];int len=0;procs(L,B,len);printf("长度是%d\n",len);SHOW(L);SHOW(B);}
