思路（经典 $O(n^2)$ 动态规划 + 前驱重构）

定义状态：$dp[i]$ 表示以位置 $i$ 结尾的严格上升子序列的最大长度。 转移方程： $dp[i]=1+\max{dp[j]\mid 0\le j<i,a_j<a_i}$，若不存在满足条件的 $j$，则 $dp[i]=1$。 为重构具体方案，额外维护前驱数组$prev[i]$为达到最优 $dp[i]$ 时所接续的前一个下标，若 $dp[i]=1$ 则 $prev[i]=-1$。

实现要点：

1. 初始化：$dp[i]\leftarrow 1$、$prev[i]\leftarrow -1$。
2. 双层循环枚举 $i$ 和 $j$，当 $a_j<a_i$ 且 $dp[j]+1>dp[i]$ 时更新 $dp[i]$ 与 $prev[i]$。
3. 扫描得到最大值 $L=\max_i dp[i]$ 及其末尾下标 $pos$，然后从 $pos$ 反向沿 $prev$ 回溯 $L$ 次并逆序，即得到一组合法的 LIS。

C++

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

// 动态规划 O(n^2) 求LIS：输出长度与一组方案
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    vector<int> dp(n, 1);    // dp[i]: 以i结尾的LIS长度
    vector<int> prev(n, -1); // prev[i]: 最优转移来自的前驱下标

    // 双层循环进行转移
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
    }

    // 找到最大长度L及其末尾位置pos
    int L = 0, pos = -1;
    for (int i = 0; i < n; ++i) {
        if (dp[i] > L) {
            L = dp[i];
            pos = i;
        }
    }

    // 回溯重构
    vector<long long> lis;
    for (int cur = pos; cur != -1; cur = prev[cur]) lis.push_back(a[cur]);
    reverse(lis.begin(), lis.end());

    // 输出
    cout << L << "\n";
    for (int i = 0; i < (int)lis.size(); ++i) {
        if (i) cout << ' ';
        cout << lis[i];
    }
    cout << "\n";
    return 0;
}

Python

# 动态规划 O(n^2) 求LIS：输出长度与一组方案
import sys

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    a = [int(next(it)) for _ in range(n)]

    dp = [1] * n        # dp[i]: 以i结尾的LIS长度
    prev = [-1] * n     # prev[i]: 达到最优时的前驱下标

    # 双层循环：尝试用更小元素的位置j来更新i
    for i in range(n):
        for j in range(i):
            if a[j] < a[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                prev[i] = j

    # 找到最大长度及其末尾位置
    L = 0
    pos = -1
    for i in range(n):
        if dp[i] > L:
            L = dp[i]
            pos = i

    # 回溯重构序列
    lis = []
    cur = pos
    while cur != -1:
        lis.append(a[cur])
        cur = prev[cur]
    lis.reverse()

    print(L)
    print(*lis)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

// 动态规划 O(n^2) 求LIS：输出长度与一组方案
public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        Integer nObj = fs.nextInt();
        if (nObj == null) return;
        int n = nObj;
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = fs.nextLong();

        int[] dp = new int[n];      // dp[i]: 以i结尾的LIS长度
        int[] prev = new int[n];    // prev[i]: 最优前驱
        Arrays.fill(dp, 1);
        Arrays.fill(prev, -1);

        // 双层循环进行状态转移
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
        }

        // 获取最大长度和末尾位置
        int L = 0, pos = -1;
        for (int i = 0; i < n; i++) {
            if (dp[i] > L) {
                L = dp[i];
                pos = i;
            }
        }

        // 回溯得到序列
        ArrayList<Long> lis = new ArrayList<>();
        for (int cur = pos; cur != -1; cur = prev[cur]) lis.add(a[cur]);
        Collections.reverse(lis);

        // 输出
        StringBuilder sb = new StringBuilder();
        sb.append(L).append('\n');
        for (int i = 0; i < lis.size(); i++) {
            if (i > 0) sb.append(' ');
            sb.append(lis.get(i));
        }
        sb.append('\n');
        System.out.print(sb.toString());
    }

    // 简易快速读入
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        Integer nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); if (c == -1) return null; } while (c <= ' ');
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') { x = x * 10 + (c - '0'); c = read(); }
            return x * sgn;
        }
        long nextLong() throws IOException {
            int c, sgn = 1;
            long x = 0;
            do { c = read(); } while (c <= ' ');
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') { x = x * 10 + (c - '0'); c = read(); }
            return x * sgn;
        }
    }
}

题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$，请你求出该序列的最长上升子序列（LIS）及其长度。 这里的上升指严格上升：即子序列中每个元素都严格大于它前一个元素。

输入描述

• 第一行包含一个整数 $n \ (1 \leq n \leq 1000)$，表示序列的长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n \ (1 \leq a_i \leq 10^9)$，表示序列中的元素。

输出描述

• 第一行输出一个整数 $L$，表示最长上升子序列的长度。
• 第二行输出 $L$ 个整数，表示你找到的一组最长上升子序列。 （若存在多个方案，输出任意一组即可。）

样例输入

6
10 9 2 5 3 7

样例输出

3
2 5 7

说明

在样例中，最长上升子序列可以是 $[2, 5, 7]$，其长度为 $3$。 其他等长方案（如 $[2, 3, 7]$）同样正确。