首页 > 代码库 > 最长下降子序列O(n^2)及O(n*log(n))解法
最长下降子序列O(n^2)及O(n*log(n))解法
求最长下降子序列和LIS基本思路是完全一样的，都是很经典的DP题目。
问题大都类似于 有一个序列 a1,a2,a3...ak..an,求其最长下降子序列（或者求其最长不下降子序列）的长度。
以最长下降子序列为例
用a[i]存储序列a的第i个元素(i: 1 to n)
用f[i]表示算上第i个位置的元素时最长子序列为f[i],
O(n^2)解法：
就是说在1 --- i -1之间必可以找到下标为j的元素a[j]使得f[j]是f[1]---f[i-1]之中最大的，则f[i] = f[j] + 1.
(注意要满足a[j]>a[i])
当i (1 to n)求得f[1] -- f[n]后只要再求得f[1]--f[n]之中最大的就是ans了。
状态转移方程：
f[i] = 1 (i = 1)//只有第一个字符
f[i] = f[j] + 1(a[i] < a[j] )//若是最长不下降则满足a[i] >= a[j].
代码实现：
//h[i]为母序列，dp[i]代表到第i个位置算上h[]i后得到的最长下降子序列长度ans是最长下降子序列长度//f[i]代表到第i个位置算上h[]i后得到的最长不下降子序列长度min?是最长不下降子序列长度#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>using namespace std;#define maxint 0x7f7f7f7fconst int N = 100000;int h[N],dp[N],f[N];int main(){ // freopen("in.txt","r",stdin); // freopen(".txt","w",stdout); int n = 1;int ans = -maxint,min = -maxint;while(scanf("%d",&h[n]) != EOF){ n ++;}dp[1] = f[1] = 1;for(int i = 1; i < n; i ++){ dp[i] = 1; f[i] = 1; for(int j = 1; j < i; j ++){ if(dp[j]+1>dp[i] && h[j] > h[i]) dp[i] = dp[j]+1; if(f[j]+1>f[i] && h[j] < h[i]) f[i] = f[j]+1; }}for(int i = 1; i < n; i ++){ if(ans<dp[i]){ ans = dp[i]; } if(min<f[i]) min = f[i];}printf("%d\n%d\n",ans,min);return 0;}
O(n*logn)解法
思路：
令数组c[k]记录使f[]= k时的a[i]的最小值，len表示此时最长下降子列的长度
在第i个位置有两种情况
1.a[i]<c[k],此时满足降序只需将a[i]接在c[k]后面，len +1;
2.a[i]>=c[k],则需要在a[1] 到c[k]之间找到一个大于它的最小值a[j]，然后将a[i]置于j+1的位置，len = k = j+1.
由于c[k]不然具有单调性因而寻找a[j]的过程可以用二分。这也就是算法复杂度达到O(n*logn)的原因。
最后len的值也就是最长子序列的长度。
代码实现：
#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>using namespace std;const int N = 1000000;//二分查找返回大于a[i]的最小值的下标int bSearch(int c[],int len,int n){int left = 1,right = len,mid;while(left <= right){ mid = (left+right)/2; if(n > c[mid]) right = mid - 1; else if(n < c[mid]) left = mid + 1; else return mid;}return left;}int a[N],c[N];int main(){ int n = 1,j,len; int count = 0; // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout);while(scanf("%d",&a[n]) != EOF){ n ++;} c[1] = a[1]; len = 1; for(int i = 1; i < n; i ++){ j = bSearch(c,len,a[i]); c[j] = a[i]; if(j > len)//没找到，说明a[i]<c[k]，根据二分查找的特点刚好j比len大一，将a[i]加到c[len+1]的位置 len = j;//更新len } printf(" ans = %d\n",len);return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。