最长递增子序列：从长度到具体下标
最长递增子序列需要保持原数组的先后顺序，但不要求位置连续。只知道最大长度，还不能告诉 DOM Diff 哪些项可以保留；这又引出具体下标的恢复问题。下面从容易验证的动态规划走到二分结尾表，再用前驱记录找回一条真实序列。
LeetCode 300：从求长度到还原具体序列
LeetCode 300「最长递增子序列」给定一个整数数组，要求返回严格递增子序列的最大长度。Diff 还多了一项要求：知道究竟保留哪些逻辑项，所以需要从「长度」继续走到「具体下标」。
例如 [10, 9, 2, 5, 3, 7, 101, 18] 的答案是 4，可以选 [2, 3, 7, 18]。递增子序列不需要连续，重复数字也不能扩展严格递增的长度；[2, 2, 2] 的答案是 1。
动态规划先给出一个容易验证的解
定义 dp[i] 为以第 i 个元素结尾的最长严格递增子序列长度。只要前面的 nums[j] < nums[i]，就可以把 nums[i] 接在那条序列后面。
// 算法示意：dp[i] 表示以 nums[i] 结尾的最大长度。
const dp = nums.map(() => 1);
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
const answer = Math.max(0, ...dp);每个位置检查此前全部位置，时间复杂度为 O(n²)，辅助空间为 O(n)。最后的 0 覆盖空数组；正式题面的输入约束可以更严格，工具函数仍可以自然处理空输入。
这个解法直接对应「以谁结尾」，也适合作为小输入的独立正确性基线。要加速，就要减少每次查找可以接在哪些前驱之后的工作。
同样长度的序列，结尾越小越容易继续接
假设当前已经找到两条长度为 3 的递增子序列，一条结尾是 8，一条结尾是 5。后来出现 6 时，只有结尾为 5 的那条能继续接；后来出现 9 时，两条都能接。对于未来可扩展性，较小的结尾不会更差。
于是维护 tails：tails[k] 表示已经处理的前缀里，长度为 k + 1 的递增子序列所能取得的最小结尾值。每读到一个新值 x，找到第一个大于等于 x 的位置并替换；找不到就追加。
这些最小结尾值按长度递增，可以通过二分定位。标准解中的核心循环如下，完整可复制的 TypeScript 函数在配套源码工作区。
最小结尾为什么递增？从一条长度为
k + 2、结尾最小的递增子序列里去掉最后一项，就得到长度为k + 1、结尾更小的候选。因此长度k + 1的最小结尾还会小于长度k + 2的最小结尾，这保证了二分所依赖的有序性。
// dom-diff-lab/copy/length-of-lis.ts:5-12（节选）
let left = 0;
let right = tails.length;
while (left < right) {
const middle = left + Math.floor((right - left) / 2);
if (tails[middle] < value) left = middle + 1;
else right = middle;
}
tails[left] = value;这里寻找的是 lower bound，即第一个 >= value 的位置。相等的值替换同一个长度的结尾，不会额外增加长度。若改成找第一个 > value 的位置，求的就会变成允许相等的最长非递减子序列，问题已经变化。
对所有长度保留最小结尾，不等于只保留一条全局看起来最小的序列。每个长度都需要一个候选；它们分别回答「如果下一步想接出这个长度，当前最容易继续的结尾是什么」。
二分替换为什么不会丢掉正确答案
设 x 被写到 tails[p]。当 p > 0 时，前一个位置的结尾严格小于 x，已经存在一条长度为 p 的递增子序列可以接上它，所以长度 p + 1 确实可达。p = 0 时，x 自己就是长度为 1 的序列。
如果原来的 tails[p] 已经存在，用不更大的 x 替换，只改善了这个长度的未来扩展条件；如果 p 位于数组末尾之外，就找到了一条比现有最长长度多 1 的序列。整个过程中，tails 的每个槽位都对应某个可达长度，最长长度也没有被较大的结尾阻挡。
因此最终 tails.length 就是答案。每项做一次二分，时间为 O(n log n)，保存最多 n 个结尾，空间为 O(n)。
| 读入值 | 处理后的 tails | 变化 |
|---|---|---|
| 10 | [10] |
建立长度 1 |
| 9 | [9] |
降低长度 1 的结尾 |
| 2 | [2] |
再次降低结尾 |
| 5 | [2,5] |
建立长度 2 |
| 3 | [2,3] |
改善长度 2 的结尾 |
| 7 | [2,3,7] |
建立长度 3 |
| 101 | [2,3,7,101] |
建立长度 4 |
| 18 | [2,3,7,18] |
改善长度 4 的结尾 |
tails 不一定是原数组中的真实子序列
上面的例子恰好让最终 tails 看起来像正确序列，但输入 [2, 3, 1] 时，tails 会先后成为 [2]、[2, 3]、[1, 3]。最后的长度 2 正确，值 [1, 3] 却不能按这个顺序从原数组里取出来，因为 1 出现在 3 之后。
要还原真实序列，可以让 tails 保存各结尾在原数组中的下标，并在处理当前元素时记录前驱下标。写入长度 p + 1 的候选时，它的前驱就是当时长度 p 的候选结尾。
对 [2, 3, 1] 来说，3 的前驱在读到 3 时就记为下标 0。后来长度 1 的候选被 1 替换，也不会把 3 已经记录的前驱改掉。最后从最长候选的末尾沿前驱回溯，得到原下标 [0, 1]，对应真实值 [2, 3]。
Vue 的
getSequence使用p = arr.slice()作为前驱记录的初始存储，再记录各候选对应的下标并回溯。复制数组本身不会把一个「乱序答案」修好；真正起作用的是处理时留下的前驱关系和最后的链式回溯。LIS 可能不唯一，Diff 只需要从中选定一条保持相对顺序的最长子序列。
逐步观察结尾、下标和前驱
演示默认使用 [2, 3, 1]，最后一步单独执行回溯。可以换成经典题面，也可以选择 Vue 中段的 [5, 4, 3, 0]，观察跳过新增标记的结果。
普通 LIS 里的 0 是合法数字，例如
[-2, 0, 1]的长度为 3。只有 Vue 的「旧下标加一」映射把 0 预留给新增项，才需要跳过它。演示中的复选框默认关闭，选择 Vue 映射案例时才开启；不能直接把 Vue 专用的忽略 0 规则复制到 LeetCode 标准答案中。
配套源码中的 lengthOfLIS 是标准长度答案，lisIndices 返回一条真实 LIS 的原数组下标。traceLIS 额外保存逐步快照以供教学，因此它的空间成本高于只返回答案的函数。
源码包中的测试用 O(n²) 动态规划作为独立基线，穷举短数组中的重复值、下降序列、负数和 0，再检查回溯下标和值都严格递增。Diff 模型还覆盖了 5 项列表的全部 120 个排列，以及交错增删的有序子集组合：设保留项数量为 r，旧位置序列的 LIS 长度为 L，验证 Vue 3 模型的移动数符合 r - L。
从算法返回到列表移动
列表重排先把保留项映射为旧位置，再找相对顺序没有改变的子序列。LIS 返回的是可以保留的相对顺序，DOM 锚点、节点创建与删除仍由渲染器处理。React、Vue 2 与 Vue 3 的同输入 Diff 对照继续比较这些策略；这里的普通算法不默认跳过数字 0。