DDOSvoid's Blog

最长上升子序列

发表于 更新于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

简介

LIS

算法

首先是最朴素的dp做法，我们令f[i]表示以a[i]结尾的最长上升子序列

转移时只需要枚举j，且a[i]>a[j]即可，时间复杂度 $O(n^2)$

其中这一部分可以用线段树等一类数据结构进行优化，可以做到 $O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdio>
#define maxn 1010
using namespace std;

int n, a[maxn]; 

int f[maxn]; 

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        f[i] = 1;
        for (int j = 1; j < i; ++j)
            if (a[i] >= a[j]) f[j] = max(f[j], f[i] + 1);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = max(ans, f[i]);
    cout << ans << endl; 
    return 0;
}

我们考虑有没有其他方法可以解决这个问题

首先必须要改动的是dp数组的定义

我们令f[i]表示长度为i的最长上升子序列的最后一位最小是什么

显然能够得到f数组是递增的

我们考虑新加入一个元素能造成什么影响

显然是找到f数组中第一个大于等于它的元素，并将那个元素替换成新加入的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 100010
using namespace std;

int n, a[maxn]; 

int d[maxn], len;  

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        if (a[i] > d[len]) d[++len] = a[i];
        else *lower_bound(d + 1, d + len + 1, a[i]) = a[i];
    } cout << len << endl; 
    return 0;
}

最长不下降子序列的话只需要稍作修改

1
2
3
4
for (int i = 1; i <= n; ++i) {
    if (a[i] >= d[len]) d[++len] = a[i];
    else *upper_bound(d + 1, d + len + 1, a[i]) = a[i];
}