会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
思路（经典 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。
实现要点：
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
