最大上升子序列，最大下降子序列，最大非增子序列，最大非减子序列

雨点打透心脏的1/2处 2021-09-30 02:00 360阅读 0赞

For example,\{1,5,2,4,3,5,6,4,7\}的最大上升子序列是\{1,2,3,5,6,7\}长度为6

现已知原序列a\[\]，如何求其最大上升子序列，最大下降子序列，最大非增子序列，最大非减子序列的长度？  
下面贴出两种方法：1.dp, 2.贪心+二分

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define maxn 1000 const int inf=1<<30; int a[maxn];//原序列 int dp[maxn];//dp[i]代表以a[i]结尾的最大非增子序列 int lnip1(int n) //动态规划，时间复杂度O(n2) { for(int i=0;i<n;i++) dp[i]=1; for(int i=1;i<n;i++) { for(int j=0;j<i;j++) { if(a[j]>=a[i])//最大非增子序列，若改为a[j]>a[i],即为最大递减子序列 { dp[i]=max(dp[j]+1,dp[i]); } } } int ans=0; for(int i=0;i<n;i++) { ans=max(ans,dp[i]); } return ans; } int b[maxn];//b[k] 记录前i个数中的长度为k的所有子序列中最后一位最小的值，b数组一定有序 int lndp(int n)//最大非递减子序列长度，时间复杂度O(nlogn) { for(int i=0;i<=n+1;i++) b[i]=inf; for(int i=0;i<n;i++) { int pos=lower_bound(b,b+i+1,a[i])-b;//如果是严格递增(lip)用upper_bound b[pos]=a[i]; } int ans; for(ans=0;b[ans]!=inf;ans++); return ans; //如果题目要求求最大非递增子序列(lnip)长度，只需先把数组反过来，再求lndp即可，最大递减类似 } int main() { int n; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; cout<<lnip1(n)<<endl; cout<<lndp(n); }

第一种方法比较简单，不做过多详解\_

下面详解第二种贪心+二分，时间复杂度位O(nlongn)的算法（注意：下面以严格上升子序列为例，请把上面代码中的lower\_bound换成upper\_bound)：

首先，

b\[maxn\] b\[k\] 记录前i个数中的长度为k+1的所有上升子序列中最后一位最小的值  
记录下最后一位最小的值，是为了能有更大的上升空间  
比如序列\{1，3，2，3，4\}  
前三个数\{1，3，2\}中长度为2的上升子序列有\{1，3\}和\{1，2\}，分别对应的b\[1\](长度为1+1=2的上升子序列的最后一位的值）为3，2，明显，选2这个较小的可以给后面的序列留下更多的上升空间，选2可以是\{1，2，3，4\}而选3只能是\{1，3，4\}，b\[k\]的值尽可能小，  
这就是其贪心的思想  
b数组一定是严格上升的，因为长度为i的最后一位最优不可能比长度为i-1的最后一位小。  
既然b数组是有序的，接下来就能用二分的方法了  
先将b的元素最大化，然后将将原序列a的元素一个一个插入到b中合适的位置--b中第一个大于a\[i\]的位置，这样如果a\[i\]能够大于b\[k\]说明a\[i\]能够放在b\[k\]（其实是b\[k\]的值对应的原序列元素）的后面，而到了第一个大于a\[i\]的位置，  
假设那个位置x上的的值为y(y可以为inf),a\[x\]=y>a\[i\],再根据上面贪心的思想，何不把结尾换为更小的值a\[i\]呢，即b\[x\]=a\[i\];  
这样插入完所有的a\[i\](其实就是将a\[i\]插在能以它为结尾的最大子序列长度的位置上），一重循环到最后一个b\[i\]!=inf,然后这个i+1就是最大上升子序列的长度

接下来再以\{1,5,2,4,3,5,6,4,7\}为例，画个图让大家理解理解：

![1250242-20170929175015778-1418162017.jpg][]

（字有点差，勿喷）

转载于:https://www.cnblogs.com/eastblue/p/7612134.html

[1250242-20170929175015778-1418162017.jpg]: /images/20210725/8e6b133a1afa4e1987c2238b0eb72c16.png