首页 > 代码库 > 最长递减子序列（转载）
最长递减子序列（转载）
Q：例如：有一个序列，例如 9 8 2 1 7 5 3 4 3 2 1.
求出最长的递减子序列。如本例的结果就是：9 8 7 5 4 3 2 1。
分析：
可采用动态规划的思想进行解答，时间复杂度为O(n^2).
设原数组为a[1....n]。另设一数组d[1....n],其中d[i]表示从第i个元素开始（一定包含第i个元素），到整个数组末尾的子序列 a[i...n]中的最长递减子序列的长度。
则本问题就是要在求出d[1]的同时，恢复出最优解。
下面给出递推式：
d[i]的值分两种情况：
1、当i=n时，d[i]=1。即最后一个元素的序列的最大递减子序列中只有它自己。
2、当i<n时，d[i]=max{d[k]| i<k<=n 且a[i]>a[k]} +1。解释意思为，包含第i个元素的序列a[i...n]的最大子序列依赖于i后面所有的序列中比a[i]小（满足递减
特性），且最大的d[k]（满足最 优特性）值再加1（加上a[i]元素）。在给d[i]赋值的时候只需记录p[i]=k,既可以作为parent属性恢复出解。
具体实现的话，开两个数组d[n],p[n]，外层循环从后往前选取i，内层循环从i往后寻找最优的k,双循环遍历即可求出所有的d[i]。然后 再进行一次O（n)操作，找出最大的d[max]。恢复解的话，可以从p[max]开始，依次恢复出各个解。
#include <iostream.h> 2 3 void longest_decrease_sub(int *a, int size) 4 { 5 6 int *d=new int[size]; //分配内存空间 7 int *p=new int[size]; //分配内存空间 8 9 d[size-1]=1;10 11 for(int i=size-1;i>=0;i--)12 { 14 int max=0; 16 int index=0;17 18 for(int j=i;j<size;j++)19 { 21 if(a[i]>a[j] && max <d[j])22 { 24 max=d[j];26 index=j; 28 }30 }31 32 if(max==0)33 {34 35 d[i]=1;36 37 p[i]=-1;38 39 }40 else41 {42 43 d[i]=max+1； 45 p[i]=index; 47 } 49 } 51 //寻找最大子序列的起始下标 53 int max=0;55 int max_index=0; 57 for( i=0;i<size;i++)58 { 60 if(d[i]>max)61 {62 63 max=d[i];64 65 max_index=i;66 67 } 69 }70 71 //从最大子序列的下标开始 输出子序列 72 cout<<"\n最长递减子序列的长度为："<<d[max_index]<<",最长子序列为："<<ends;73 74 for( i=max_index;i!=-1;i=p[i])75 {76 77 cout<<a[i]<<" "<<ends;78 79 }80 81 delete [] d;82 83 delete [] p;84 85 }86 87 void main()88 {89 int data[10]={1,2,5,4,3,2,7,8,9,0};90 longest_decrease_sub(data,10);91 }
另外一个代码版本：
1 #include <iostream> 2 #include <vector> 3 using namespace std; 4 5 6 int main() 7 { 8 int n,m; 9 cin>>n;10 while (n--) {11 cin>>m;12 vector<int>b(m);13 vector<int>f(m);14 for(int i=0;i<m;i++)15 {16 cin>>b[i];17 f[i]=1;18 }19 for(int i=1;i<m;i++)20 for(int j=0;j<i;j++)21 {22 if(b[j]>=b[i]&&f[j]+1>f[i])23 f[i]=f[j]+1;24 }25 int max=1;26 for(int i=0;i<m;i++)27 {28 if(f[i]>max)29 max=f[i];30 }31 cout<<max<<endl;32 }33 return 0;34 }
最长递减子序列（转载）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。