这其中最长的递增序列为(35，36，39，42)和(3，15，27，42)，所以序列A的最长递增子序列的长度为4，同时在A中长度为4的递增子序列不止一个。
该算法的思想十分简单，如果要得出Ai序列的最长递增子序列，就需要计算出Ai-1的所有元素作为最大元素的最长递增序列，依次递推Ai-2，Ai-3，……，将此过程倒过来，即可得到递推算法，依次推出A1，A2，……，直到推出Ai为止，
#include<bits/stdc++.h> using namespace std; int a[100001],b[100001],c[10001]; int main(){ int n,i=0,l=0; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } b[0]=1; c[0]=1; for(int j=1;j<n;j++){ b[j]=1;c[j]=1; for(int k=0;k<j;k++){ if(a[j]>a[k]&&b[k]+1>b[j]){ b[j]=b[k]+1; //cout<<j<<"="<<b[j]<<endl; } } } int mx=0;int mi=0; for(int j=0;j<n;j++){ if(b[j]>mx) mx=b[j]; } cout<<mx<<endl; } 计算出长度为length的array的最长递增子序列的长度，作为返回值返回，实际序列保存在result数组中，该函数中使用到了C99变长数组参数特性（这个特性比较赞），不支持C99的同学们可以用malloc来申请函数里面的两个数组变量。函数的时间复杂度为O(nn)，下面我们来介绍可以将时间复杂度降为O(nlogn)改进算法。
在基本算法中，我们发现，当需要计算前i个元素的最长递增子序列时，前i-1个元素作为最大元素的各递增序列，无论是长度，还是最大元素值，都毫无规律可循，所以开始计算前i个元素的时候只能遍历前i-1个元素，来找到满足条件的j值，使得aj < ai，且在所有满足条件的j中，以aj作为最大元素的递增子序列最长。有没有更高效的方法，找到这样的元素aj呢，实际是有的，但是需要用到一个新概念。在之前我举的序列例子中，我们会发现，当计算到第10个元素时，前9个元素所形成最长子序列分别为
35 35，36 35，36，39 3 3，15 3，15，273，6
这其中长度为3的子序列有两个，长度为2的子序列有3个，长度为1的子序列2个，所以一个序列，长度为n的递增子序列可能不止一个，但是所有长度为n的子序列中，有一个子序列是比较特殊的，那就是最大元素最小的递增子序列（挺拗口的概念），在上述例子中，序列(3)，(3,6)，(3，5，27)就满足这样的性质，他们分别是长度为1，2，3的递增子序列中最大元素最小的（截止至处理第10个元素之前），随着元素的不断加入，满足条件的子序列会不断变化。如果将这些子序列按照长度由短到长排列，将他们的最大元素放在一起，形成新序列B{b1,b2,……bj}，则序列B满足b1 < b2 < …… <bj。这个关系比较容易说明，假设bxy表示序列A中长度为x的递增序列中的第y个元素，显然，如果在序列B中存在元素bmm > bnn，且m < n则说明子序列Bn的最大元素小于Bm的最大元素，因为序列是严格递增的，所以在递增序列Bn中存在元素bnm < bnn，且从bn0到bnm形成了一个新的长度为m的递增序列，因为bmm > bnn，所以bmm > bnm，这就说明在序列B中还存在一个长度为m，最大元素为bnm < bmm的递增子序列，这与序列的定义，bmm是所有长度为m的递增序列中第m个元素最小的序列不符，所以序列B中的各元素严格递增。发现了如此的一个严格递增的序列，这让我们柳暗花明，可以利用此序列的严格递增性，利用二分查找，找到最大元素刚好小于aj的元素bk，将aj加入这个序列尾部，形成长度为k+1但是最大元素又小于bk+1的新序列，取代之前的bk+1，如果aj比Bn中的所有元素都要大，说明发现了以aj为最大元素，长度为n+1的递增序列，将aj做Bn+1的第n+1个元素。从b1依次递推，就可以在O(nlogn)的时间内找出序列A的最长递增子序列。
理论说明比较枯燥，来看一个例子，以序列{6，7，8，9，10，1，2，3，4，5，6}来说明改进算法的步骤：程序开始时，最长递增序列长度为1（每个元素都是一个长度为1的递增序列），当处理第2个元素时发现7比最长递增序列6的最大元素还要大，所以将6，7结合生成长度为2的递增序列，说明已经发现了长度为2的递增序列，依次处理，到第5个元素(10)，这一过程中B数组的变化过程是
6 6，7 6，7，8 6，7，8，9 6，7，8，9，10开始处理第6个元素是1，查找比1大的最小元素，发现是长度为1的子序列的最大元素6，说明1是最大元素更小的长度为1的递增序列，用1替换6，形成新数组1，7，8，9，10。然后查找比第7个元素(2)大的最小元素，发现7，说明存在长度为2的序列，其末元素2，比7更小，用2替换7，依次执行，直到所有元素处理完毕，生成新的数组1，2，3，4，5，最后将6加入B数组，形成长度为6的最长递增子序列.
这一过程中，B数组的变化过程是 1，7，8，9，10 1，2，8，9，10 1，2，3，9，10 1，2，3，4，10 1，2，3，4，5 1，2，3，4，5，6当处理第10个元素(5)时，传统算法需要查看9个元素(6,7,8,9,10,1,2,3,4)，而改进算法只需要用二分查找数组B中的两个元素(3, 4)，可见改进算法还是很阴霸的。
下面是该算法的实现： #include<bits/stdc++.h> using namespace std; int a[10]={1,5,3,6,9,8,4,6,8,10}; int b[100]={0}; int binary_search(int n,int s){ //二分查找位置 int l=0; int r=s-1; int mid; while(l<r){ mid=(l+r)/2; if(n>b[mid]) l=mid+1; else if(n<mid) r=mid-1; else return mid; } return r; //返回值很重要 } int main(){ int l=0; b[l]=a[0]; for(int j=1;j<10;j++){ if(a[j]>b[l]){ b[++l]=a[j]; } else{ int k=binary_search(a[j],l+1); b[k]=a[j]; } } cout<<l+1<<endl; //输出记得加 1 }