信息学竞赛模板（十七）— 最长上升子序列

2021-12-19 · 64次阅读 · 原创 · 数据结构与算法

定义

最长上升子序列（Longest Increasing Subsequence），简称LIS，也有些情况求的是最长非降序子序列，二者区别就是序列中是否可以有相等的数。

模板代码

1. 动态规划

复杂度 $O(n^2)$

#include<bits/stdc++.h>
using namespace std;

const int N = 1005;
int n, ans, a[N], f[N];
//a为原数组，f记录前i个数中以a[i]结尾的最长上升子序列长度

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

2. 动态规划+二分查找

复杂度 $O(n\times logn)$

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, ans, a[N], b[N];
//a为原数组，b[i]为当前情况下长度为 i 的上升子序列的最小结尾
//len为当前最长上升子序列的最大长度

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
    int len = 1;
    b[1] = a[1];
    for(int i = 2; i <= n; i++) {
        if(a[i] > b[len]) b[++len] = a[i];
        else {
            int id = lower_bound(b + 1, b + len + 1, a[i]) - b;
            b[id] = a[i];
        }
    }
    cout << len << endl;
    
    return 0;
}

简写模板

template<typename T>
int lis(vector<T> a) {
    vector<T> dp;
    for(auto x : a) {
        auto it = upper_bound(dp.begin(), dp.end(), x); // > : lower, >= : upper
        if(it == dp.end()) dp.push_back(x);
        else *it = x;
    }
    return dp.size();
}

例题

标题：	信息学竞赛模板（十七）— 最长上升子序列
链接：	https://www.fightingok.cn/detail/180
更新：	2022-09-18 22:45:56
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可

信息学竞赛模板（十七）— 最长上升子序列

定义

模板代码

1. 动态规划

2. 动态规划+二分查找

例题

Cyan