最长上升子序列

题目描述

给定长度为 $N$ （ $1 \le N \le 1000$ ）的整数序列 $(a_1,a_2,\dots,a_N)$ ，取下标严格递增的子序列 $i_1 < i_2 < \dots < i_K$ ，要求元素严格递增 $a_{i_1} < a_{i_2} < \dots < a_{i_K}$ ，求最大的 $K$ 。每个元素取值范围 $0 \sim 10000$ 。

样例输入 7 / 1 7 3 5 9 4 8，其中 $1<3<5<8$ 是一条最长上升子序列，输出 $4$ 。

思路

维护 tails[L] 表示长度 $L$ 的上升子序列的最小结尾；扫描序列时，对每个值 v 在严格递增的 tails 上二分找第一个 >= v 的位置，能追加就追加，否则原地替换更小结尾；每个元素一次二分， $O(N \log N)$ 得到 LIS 长度。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 03:02
# update_at: 2026-09-30 03:02

import sys
from bisect import bisect_left


def lis_length(seq: list[int]) -> int:
    """严格上升子序列的最长长度：tails[i] 记录长度 i+1 的最小可能结尾。"""
    tails: list[int] = []
    for value in seq:
        # 等值元素接不上（必须严格上升），故与等值位置交换，保住更小的结尾
        pos = bisect_left(tails, value)
        if pos == len(tails):
            tails.append(value)  # 能延长所有上升子序列
        else:
            tails[pos] = value   # 同长度下结尾更小，后续更容易接
    return len(tails)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    length = next(data)                 # 题面的 n
    seq = [next(data) for _ in range(length)]
    print(lis_length(seq))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
48/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 07:50
 * update_at: 2026-10-05 07:50
 */

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 1005; // N ≤ 1000，留一点裕量

int n;
int a[MAXN]; // 序列元素，值域 0..10000，用 int 足够

// tails[k] 表示当前已扫描前缀中，长度为 k+1 的上升子序列的最小可能结尾。
// tails 始终严格递增，长度上限等于 LIS 长度 ≤ N。
int tails[MAXN];
int len_t; // tails 当前有效长度

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    len_t = 0;
    for (int i = 1; i <= n; i++) {
        int v = a[i];
        // 在严格递增的 tails 中找第一个 >= v 的位置（lower_bound），等值只能替换不追加
        int pos = lower_bound(tails, tails + len_t, v) - tails;
        if (pos == len_t) {
            tails[len_t++] = v; // 比所有层结尾都大，LIS 长度 +1
        } else {
            tails[pos] = v;     // 同长度下结尾更小，后续更容易接
        }
    }

    cout << len_t << "\n";
    return 0;
}

目录

题目描述

思路

参考代码