找出由n个数组成的序列的最长单调递增子序列
解法一:转化成LCS问题求解,时间复杂度为O(n*n).
思路:原序列为A,把A按升序排序得到序列B,求出A,B序列的最长公共子序列,即为A的最长单调递增子序列。
#include<iostream> #include<algorithm> #include<string> #include<cstdio> using namespace std; //转化成LCS问题,时间复杂度O(n*n) int d[105][105]; int a[105]; int b[105]; int c[105][105]; void LCS_path(int i,int j) //打印路径 { if(i==0||j==0) return; if(c[i][j]==1) { LCS_path(i-1,j-1); cout<<a[i]<<" "; //a[i]==b[j] } else if(c[i][j]==2) { LCS_path(i-1,j); } else { LCS_path(i,j-1); } } int main() { int i,j,n,m; //freopen("d:\\test.txt","r",stdin); cin>>m; while(m--) { cin>>n; for(i=1; i<=n; i++) { cin>>a[i]; b[i]=a[i]; } sort(b+1,b+n+1); for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { if(a[i]==b[j]) { d[i][j]=1+d[i-1][j-1]; c[i][j]=1; } else if(d[i-1][j]>d[i][j-1]) { d[i][j]=d[i-1][j]; c[i][j]=2; } else { d[i][j]=d[i][j-1]; c[i][j]=3; } } } LCS_path(n,n); cout<<endl; cout<<d[n][n]<<endl; } //fclose(stdin); return 0; }
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; int d[105]; int a[105]; int main() { int i,j,n,m; //freopen("d:\\test.txt","r",stdin); cin>>m; while(m--) { cin>>n; for(i=0; i<n; i++) { cin>>a[i]; } d[0]=1; int ans=0; for(i=1;i<n;i++) { int Max=0; for(j=i-1;j>=0;j--) { if(a[i]>a[j]) { if(Max<d[j]) Max=d[j]; } } d[i]=Max+1; ans=max(ans,d[i]); } cout<<ans<<endl; } //fclose(stdin); return 0; }
在给定状态 i 时,可用二分查找找到满足g[k]>=a[i]的第一个下标k,d[i]=k,此时a[i]<g[k],而d[i]=k,所以更新g[k]=a[i]. 时间复杂度O(nlogn).
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; const int INF=1e9; int d[105]; int a[105]; int g[105]; int main() { int i,j,n,m; //freopen("d:\\test.txt","r",stdin); cin>>m; while(m--) { cin>>n; for(i=0; i<n; i++) { cin>>a[i]; } int ans=0; for(i=1;i<=n;i++) g[i]=INF; //初始化g[i] for(i=0;i<n;i++) { int k=lower_bound(g+1,g+1+n,a[i])-g; d[i]=k; g[k]=a[i]; //更新g[k],使g数组保持最小递增序列(第1~n个元素均为当前可取最小值),不会丢失最优解 ans=max(d[i],ans); } cout<<ans<<endl; } //fclose(stdin); return 0; }
原文:http://blog.csdn.net/u012198382/article/details/25001663