代码与动画 LONGEST INCREASING SUBSEQUENCE
最长递增子序列.
为每个元素寻找可接续的前驱，记录长度并还原递增子序列。
时间 O(n²)空间 O(n)严格递增
原理与执行逻辑
为每个元素求出以它结尾的最长严格递增子序列。查看之前更小的元素，把它们的最佳长度加一作为候选，并记录带来改进的前驱。
执行步骤
- 所有 dp 初始化为 1，前驱初始化为 -1。
- 对当前 i 枚举 j < i，仅考虑 a[j] < a[i]。
- dp[j] + 1 更大时更新 dp[i] 与前驱 j，并维护最佳末尾。
- 沿最佳末尾的前驱链向前回溯，逆序后得到一个递增子序列。
关键理解
dp[i] 的序列必须以 i 结尾，最终答案取所有 dp 的最大值。严格递增排除相等值；前驱记录与长度更新必须同步。
简短示例
[3, 1, 2, 4] 对应长度 [1, 1, 2, 3]；最后的 4 接续 2，回溯得到 [1, 2, 4]。
代码与执行动画
STEP 0 / 40function lis(a) { const dp = Array(a.length).fill(1), previous = Array(a.length).fill(-1); let best = 0; for (let i = 0; i < a.length; i++) { for (let j = 0; j < i; j++) { if (a[j] < a[i] && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; previous[i] = j; } } if (dp[i] > dp[best]) best = i; } const sequence = []; for (let i = best; i !== -1; i = previous[i]) sequence.push(a[i]); return sequence.reverse();}当前数据正在操作已访问 / 命中标记 / 指针
0
初始化递增长度
每个元素自身构成长为 1 的序列，前驱为 -1。
配置演示数据
应用后重新生成执行过程，可单步观察结果。
最长递增子序列的操作规则
dp[i] 是以第 i 个元素结尾的最长长度。相等元素不能接续；使用前驱下标回溯一个最优解。这里展示二次 DP，不采用二分优化。
对应题目与扩展练习
观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。
- 对应题目300. 最长递增子序列打开题目
直接对应严格递增子序列；进阶可比较 O(n²) DP 与 O(n log n) 方法。
同时维护最优长度与对应方案数量。