【例9.3】求最长不下降序列

题目描述

给定 $n(1 \leq n \leq 200)$ 个互不相同整数，求最长不下降子序列长度。输入一行 $n$ 和一行 $n$ 个整数，输出 max=最大长度。样例：输入 14 与 13 7 9 16 38 24 37 18 44 19 21 22 63 15，输出 max=8。

思路

设 $f_i$ 为以第 $i$ 个数结尾的最长不下降子序列长度。枚举 $j<i$ 且 $b_j \leq b_i$ 的位置，用 $f_j+1$ 更新 $f_i$ ，答案取 $\max f_i$ 。 $O(n^2)$ 足够。

参考代码

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
34#!/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 02:21
# update_at: 2026-09-30 02:21

import sys

# 输出的前缀大小写以评测数据为准：题面样例写 "max=8"，官方归档参考答案写 "Max=19"。
MAX_PREFIX = "Max="


def longest_lengths(seq: list[int]) -> list[int]:
    """f[i] = 以 seq[i] 结尾的最长不下降子序列长度 = 1 + max{f[j] : j < i 且 seq[j] <= seq[i]}。"""
    f = [1] * len(seq)
    for i, value in enumerate(seq):
        # default=0 表示前面没有能接上的元素，当前元素自己起头，长度就是 1
        f[i] = 1 + max((f[j] for j in range(i) if seq[j] <= value), default=0)
    return f


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 题面的序列长度
    seq = [next(data) for _ in range(n)]
    # 题面还要求第二行输出一条最长不下降子序列，但归档的参考答案只保存了长度这一行
    # （data/*.out 里就是 "Max=19\n" 这样的 7 个字节），多写第二行反而对不上，
    # 所以这里只输出长度；带回溯的完整写法见 index.md。
    print(f"{MAX_PREFIX}{max(longest_lengths(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/**
 * 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:20
 * update_at: 2026-10-05 07:24
 */
#include <cstdio>
#include <iostream>

using namespace std;

typedef long long ll;

const int MAXN = 205;

int n;
ll b[MAXN];      // 输入序列
int f[MAXN];     // f[i] 表示以 b[i] 结尾的最长不下降子序列长度

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

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> b[i];

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = 1; // 至少包含自身
        for (int j = 1; j < i; ++j) {
            if (b[j] <= b[i] && f[j] + 1 > f[i]) {
                f[i] = f[j] + 1;
            }
        }
        if (f[i] > ans) ans = f[i];
    }

    // 本题归档答案只要求输出长度行
    cout << "max=" << ans << "\n";
    return 0;
}

【例9.3】求最长不下降序列

目录

题目描述

思路

参考代码