最长单调子序列

最长上升子序列(LIS)

问题描述:

​ 给你一个序列,让你求出其中的最长的上升子序列。

​ 比如数组{1,5,3,2,4},其最长递增子序列为{1,3,4}或{1,2,4}。

dp求解(小范围数据)

在长度 n 较小的情况下,我们可以用dp的方式来求解,复杂度为O(n^2) :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n;
int dp[maxn];
int a[maxn];
int LIS(){
int res=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(a[i]<a[j]) dp[j]=max(dp[j],dp[i]+1);
//如果是最长非递减的话,则if(a[i]<=a[j])
}
res=max(res,dp[i]);
}
return res+1;
}

这个理解起来还算容易:当我们求出前m(m<=n)个数的LIS长度时,那么我们就可以求出当前状态下m后面的数的最长长度。

因为m和m+1之间没有其他的数字,所以我们可以认为我们求出了前m+1个数的LIS长度。

然后依次递推,就可以求出n个数的LIS。

dp求解(大范围数据)

当n比较大时,O(N^2)的时间复杂度明显没办法满足需要,所以我们需要更高效的方法。

当我们循环遍历时,我们可以把当前的最长的LIS存储下来。

对于样例{1,5,3,2,4},我们储存的顺序依次为:

{1},

{1,5}

{1,3}

{1,2}

{1,2,,4}

这个刚开始理解起来比较难理解。对于第二步{1,5}来说,当前的LIS长度为2,由LIS的特性可知,我们希望前面的元素尽量的小。

所以当遍历到第三个元素时,由于{1,5},{1,3}长度均为2,但我们更希望值小一点,所以我们就用3来代替了5的值。

第四个元素也一样。

第五个元素{4},由于当前我们保存的LIS{1,2}最大值小于4,因此我们就把4放进来,所以最终结果就为3。

注意:储存的元素并不是LIS的值,这个储存的值只是用来寻找LIS的。

再来看一个样例:{1,3,5,4,6,2},存储的顺序依次为:

{1}

{1,3}

{1,3,5}

{1,3,4}

{1,3,4,6}

{1,2,4,6}

对于第6步,因为2<6,所以我们一定能找到替换2的元素。而我们希望储存的序列尽可能的小,所以我们需要找到2能替换的最小的元素。因此我们的替换操作为3 -> 2。

这一步可以理解为:找到储存的序列中比当前元素大(或者相等)的第一个元素,进行替换

因为我们在储存时保证了储存的元素单调,因此我们在寻找替换位置时可以用高效的二分法,所以这种方法的复杂度为O( n*log(n) )。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int n;
int dp[maxn];
int a[maxn];
int find(int x){
int l=0,r=n-1,mid;
while(l<r){
mid=(l+r)/2;
if(dp[mid]<x){//小于的话肯定不是被替换的元素,因此可以+1
l=mid+1;
}
else{//大于等于的情况下这个元素可能是被替换的元素,所以我们不能忽略这个元素
r=mid;
}
}
return l;
}
int LIS(){
fill(dp,dp+n,INF);//将dp里面的元素全部替换为INF
for(int i=0;i<n;i++){
int pos=find(a[i]);
dp[pos]=a[i];
}
int res=find(INF);
return res;
}

输出LIS的元素

在前面已经说过,储存的值并不是LIS的元素,那么我们如何来输出LIS呢?

前面已经说过,我们的操作都是找到储存的序列中第一个比当前元素大(或者相等)的位置,那么这个元素的前面一个元素一定是它左边的那个元素,因此我们需要用一个数组来储存每个元素的前驱。

因此我们在上面的代码上做一些小修改:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int n;
int dp[maxn];
int a[maxn];
int pre[maxn];//用来记录每个元素的前驱
void output(int x){//用来输出LIS的元素(可能有多个答案,这里只取其中一种)
if(pre[x]!=0) output(pre[x]);
printf("%d ",x);
}
int find(int x){
int l=0,r=n-1,mid;
while(l<r){
mid=(l+r)/2;
if(dp[mid]<x){//小于的话肯定不是被替换的元素,因此可以+1
l=mid+1;
}
else{//大于等于的情况下这个元素可能是被替换的元素,所以我们不能忽略这个元素
r=mid;
}
}
return l;
}
int LIS(){
fill(dp,dp+n,INF);//将dp里面的元素全部替换为INF
for(int i=0;i<n;i++){
int pos=find(a[i]);
dp[pos]=a[i];
pre[ dp[pos] ]=dp[pos-1];//当前元素所对应的前一个元素的值。
}
int res=find(INF);
output(dp[res-1]);
return res;
}

这样,我们就可以输出LIS的元素了。

最长下降子序列(LDS)

最长下降子序列求解方法和LIS相似,只需要把元素的位置翻一下即可求解。

感谢您的支持
-------------本文结束感谢您的阅读-------------