首页 > 代码库 > 最长递增子序列
最长递增子序列
方法一：
用LCS的方法，计算序列a与排序后的序列b之间的最长公共子序列。在这里用了快速排序，然后再用LCS方法。
void quiksort(int a[],int start,int end){ int temp=a[start]; int i=start,j=end; if(i<j) { while(i<j) { while(i<j&&a[j]>temp) j--; a[i]=a[j]; while(i<j&&a[i]<temp) i++; a[j]=a[i]; } a[j]=temp; quiksort(a,start,i-1); quiksort(a,i+1,end); }}int LCS(int a[],int b[],int len){ vector<int> f(len+1,0); for(int i=1;i<=len;i++) for(int j=1;j<=len;j++) { f[j]=a[i-1]==b[j-1]?f[j-1]+1:max(f[j],f[j-1]); } return f[len];}
方法二：
动态规划，用F[i]表示以a[i]结尾的递增子序列的最大长度。那么
F[i]=max(F[j])+1,其中a[j]<a[i]&&j<i, j取0~i之间的所有值；最后求所有的F[i]的最大值； 该方法的时间复杂度为O(N2)
int dp(int a[],int len){ vector<int> f(len,1); for(int i=1;i<len;i++) { for(int j=0;j<i;j++) f[i]=a[j]<a[i]?max(f[i],f[j]+1):f[i]; } int result=1; for(int i=0;i<len;i++) result=max(result,f[i]); return result;}
方法三：
定义一个f(n)存储对应长度的LIS的最小末尾。如f(0)存储着长度为1的LIS的最小末尾，f(1)存储着长度为2的LIS的最小末尾。
例如对于序列a[9]={2,1,5,3,6,4,8,9,7}，len记录f序列的长度。
首先f[0]=a[0]=2，len=1;
再把a[1]插入f序列，a[1]< f[0],因此f[0]=a[1]=1; len还是为1；
再把a[2]插入f序列，a[2]> f[0],因此f[1]=a[2]=5; len=2；
再把a[3]插入f序列，a[3]< f[1],因此将a[3]插到f[1]的位置。f[1]=a[3]=3;len还是2
再把a[4]插入f序列，a[4]> f[1],因此将a[4]插到f[2]的位置。f[2]=a[4]=6; f序列的长度变长了，len是3
再把a[5]插入f序列，a[5]< f[2],因此将a[5]插到f[2]的位置。f[2]=a[5]=4;len还是3
再把a[6]插入f序列，a[6]> f[2],因此将a[6]插到f[3]的位置。f[3]=a[6]=8; f序列的长度变长了，len是4
再把a[7]插入f序列，a[7]> f[3],因此将a[7]插到f[4]的位置。f[4]=a[7]=9; f序列的长度变长了，len是5
再把a[8]插入f序列，a[8]< f[4],因此将a[8]插到f[3]的位置。f[3]=a[8]=7;len还是5
在这里我们使用二分查找的方法找到每个a[i]应该插入到f序列的什么位置。若a[i]大于f序列此时的最后一个元素，那么只需要将a[i]插入到序列f的末尾，否则使用二分查找法插入a[i]; f[i]中存储的是长度为i+1的递增子序列的最小末尾的值。此方法的时间复杂度为O(NlogN)
int bfind(vector<int> a,int len,int num){ int start=0; int end=len-1; while(start<=end) { int mid=(start+end)/2; if(a[mid]==num) return mid; else if(a[mid]>num) end=mid-1; else start=mid+1; } return start;}int nlogn(int a[],int n){ vector<int> f(n); f[0]=a[0]; int len=1; for(int i=1;i<n;i++) { if(f[len-1]<a[i]) { f[len]=a[i]; len++; } else { int pos=bfind(f,len,a[i]); f[pos]=a[i]; } } return len;}
对于以上三种方法的测试实现代码如下：
其中主函数len1输出的为方法一的结果；
len2输出的是方法二的结果；
len3输出的是方法三的结果；
#include<iostream>#include<vector>using namespace std;void quiksort(int a[],int start,int end){ int temp=a[start]; int i=start,j=end; if(i<j) { while(i<j) { while(i<j&&a[j]>temp) j--; a[i]=a[j]; while(i<j&&a[i]<temp) i++; a[j]=a[i]; } a[j]=temp; quiksort(a,start,i-1); quiksort(a,i+1,end); }}int LCS(int a[],int b[],int len){ vector<int> f(len+1,0); for(int i=1;i<=len;i++) for(int j=1;j<=len;j++) { f[j]=a[i-1]==b[j-1]?f[j-1]+1:max(f[j],f[j-1]); } return f[len];}int dp(int a[],int len){ vector<int> f(len,1); for(int i=1;i<len;i++) { for(int j=0;j<i;j++) f[i]=a[j]<a[i]?max(f[i],f[j]+1):f[i]; } int result=1; for(int i=0;i<len;i++) result=max(result,f[i]); return result;}int bfind(vector<int> a,int len,int num){ int start=0; int end=len-1; while(start<=end) { int mid=(start+end)/2; if(a[mid]==num) return mid; else if(a[mid]>num) end=mid-1; else start=mid+1; } return start;}int nlogn(int a[],int n){ vector<int> f(n); f[0]=a[0]; int len=1; for(int i=1;i<n;i++) { if(f[len-1]<a[i]) { f[len]=a[i]; len++; } else { int pos=bfind(f,len,a[i]); f[pos]=a[i]; } } return len;}int main(){ int a[9]={2,1,5,3,6,4,8,9,7}; int b[9]; for(int i=0;i<9;i++) { b[i]=a[i]; } quiksort(a,0,8); int len=LCS(a,b,9); cout<<len<<endl; int len2=dp(b,9); cout<<len2<<endl; int len3=nlogn(b,9); cout<<len3<<endl;} 
最长递增子序列