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

发表于 |

最长递增子序列最常规的做法是 $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
28
#include <cstdio>
using namespace std;
/*------ Welcome to visit blog of dna049: http://dna049.com ------*/
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
45
46
47
#include <cstdio>
#include <iostream>
using namespace std;
/*------ Welcome to visit blog of dna049: http://dna049.com ------*/
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(){
    freopen("/Users/dna049/Desktop/AC/in","r",stdin);
//    freopen("/Users/dna049/Desktop/AC/out","w",stdout);
    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;
}