最长递增子序列与连续子序列最大和

最长递增子序列最常规的做法是 $O(n^2)$ 的动态规划(dp) 做法(很容易想到不多说了)。这里可以维护一个单调的数列使其复杂度降至 $O(n \log n)$。相应的最长递减、不升、不降子序列完全类似,相应修改即可。另外,这个问题让我想起另一个降低复杂度的经典例子:连续子序列最大和。从 $O(n^3)$ 到 $O(n^2)$ 再到 $O(n)$.

最长递增子序列

假设

我们用数组 $a$ 表示原始数列。用 $b[k]$ 表示长度为 $k$ 的不降子序列中尾数最小值。那么显然数组 $b$ 是单调递增的。初始状态 $b[1]=a[1],k=1$

维护

若 $a[i]>b[k]$,则 $k=k+1,b[k]=a[i]$;否则,找到二分最小的 $j$ 使得 $b[j] \geq a[i]$ 然后 $b[j]=a[i]$。最终答案就是 $k$。

例题:POJ 2533

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
#include <cstdio>
using namespace std;
int LIS(int a[],int n){ // longest increasing subsquence for 0 ~ n-1
if(n<=0) return 0;
int *b = new int[n];
b[0]=a[0];
int k=0;
for(int i=1;i!=n;++i){
if(a[i]>b[k]) b[++k]=a[i];
else b[lower_bound(b,b+k,a[i])-b]=a[i];
}
return k+1;
}
// lower_bound(first,end,val) 表示在单增 [frist,end) 中首次大于等于 val 的位置
// upper_bound(first,end,val) 表示在单增 [frist,end) 中首次大于 val 的位置
const int N= 1003;
int a[N];
int main(){
int n;
while(~scanf("%d",&n)){
for(int i=0;i!=n;++i){
scanf("%d",a+i);
}
printf("%d\n",LIS(a,n));
}
return 0;
}

记录子序列的做法

由于同学的需要,这里给出加强版:记录子序列
首先我们定义一下变量,$a,b$ 已经说过,用 $c[i]$ 表示 $b[i]$ 元素所在的位置。$p[i]$ 表示 $i$ 前面一个元素所在位置。那么最后的子序列就是以 $b[k]$ 所在位置为结尾位置,再用 $p[i]$ 来回溯得到的序列(见代码)

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
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <iostream>
using namespace std;
const int N= 1003;
int a[N],c[N],p[N],sa[N];
int LIS(int n){ // longest increasing subsquence for 0 ~ n-1
if(n<=0) return 0;
int *b = new int[n];
b[0]=a[0];c[0]=0;p[0]=0;
int k=0;
for(int i=1;i!=n;++i){
if(a[i]>b[k]){
p[i]=c[k];
c[++k]=i;
b[k]=a[i];
}else{
int tmp = int(lower_bound(b,b+k,a[i])-b);
b[tmp]=a[i];
c[tmp]=i;
p[i]=tmp>0?c[tmp-1]:i;
}
}
int x = c[k];
for(int i=k;i>=0;--i){
sa[i]=a[x];
x=p[x];
}
return k+1;
}
int main(){
int n;
while(~scanf("%d",&n)){
for(int i=0;i!=n;++i){
scanf("%d",a+i);
}
int k = LIS(n);
printf("%d\n",k);
for(int i=0;i<k;++i){
cout<<sa[i]<<" ";
}
cout<<endl;
}
return 0;
}

连续子序列最大和

$O(n^3)$ 实在不值一提。$O(n^2)$ 就是先预处理前 $m$ 项和。这里具体讲两种 O(n) 的做法。

  1. 遍历序列对s进行累加,如果$s<0$,将 $s$ 重置为$0$,每次更新$s$ 的最大值。最后便能求出最大值(注意序列中全为负数的情况)
  2. 设 $dp[i]$ 表示尾为 $i$ 的最大和。那么 $dp[i]=\max (dp[i-1],a[i])$ 。

上述两种做法本质上是一致的,做法2可能更好理解。并且其实实现的时候我们没必要去用数组标记。

代码

1
2
3
4
5
6
7
8
9
10
int MSCS(int a[],int n){ // maximal sum of continue subsquence,mind overflow
if(n<=0) return 0;
int r=a[0],s=a[0];
for(int i=1;i!=n;++i){
s = max(s,0);
s += a[i];
r = max(r,s);
}
return r;
}
如有帮助,烦请资瓷(一块也是爱0.0)