思路（经典 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。
实现要点：
题目描述
给定一个长度为 n 的整数序列 a1,a2,…,an，请你求出该序列的最长上升子序列（LIS）及其长度。
这里的上升指严格上升：即子序列中每个元素都严格大于它前一个元素。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
