思路（经典 O(n2) 动态规划 + 前驱重构）
定义状态：dp[i] 表示以位置 i 结尾的严格上升子序列的最大长度。
转移方程：
dp[i]=1+maxdp[j]∣0≤j<i,aj<ai，若不存在满足条件的 j，则 dp[i]=1。
为重构具体方案，额外维护前驱数组prev[i]为达到最优 dp[i] 时所接续的前一个下标，若 dp[i]=1 则 prev[i]=−1。
实现要点：
P3901.最长上升子序列（具体方案）
题目描述
给定一个长度为 n 的整数序列 a1,a2,…,an，请你求出该序列的最长上升子序列（LIS）及其长度。
这里的上升指严格上升：即子序列中每个元素都严格大于它前一个元素。
输入描述
- 第一行包含一个整数 n (1≤n≤1000)，表示序列的长度。
- 第二行包含 n 个整数 a1,a2,…,an (1≤ai≤109)，表示序列中的元素。
输出描述
- 第一行输出一个整数 L，表示最长上升子序列的长度。
- 第二行输出 L 个整数，表示你找到的一组最长上升子序列。
（若存在多个方案，输出任意一组即可。）
样例输入
6
10 9 2 5 3 7
样例输出
3
2 5 7
说明
在样例中，最长上升子序列可以是 [2,5,7]，其长度为 3。
其他等长方案（如 [2,3,7]）同样正确。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
