思路（经典 $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$。

实现要点：

题目描述

给定一个长度为 $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]$）同样正确。