# 最长递增子序列 **基本介绍** 最长递增子序列（Longest Increasing Subsequence，简称 LIS）是计算机科学中一个经典的算法问题。这看上去是很难的一个词语，遇到这种词，最简单的方法就是拆词，这里可以拆为 3 个词：**最长**、**递增**、**子序列**。 1. 子序列 ```js [1, 2, 3, 4, 5] ``` 子序列有多个： ```js [1, 2, 3] [1, 3] [2, 4, 5] ``` 2. 递增 ```js [2, 1, 5, 3, 6, 4, 8, 9, 7] ``` 这个子序列里面的元素必须是递增的： ```js [1, 5] // 子序列，并且是递增的 [1, 3, 6] // 子序列，并且是递增的 [2, 1, 5] // 子序列，但是不是递增的 ``` 3. 最长 相当于在上面的基础上，有增加了一个条件，需要是最长的、递增的子序列 ```js [2, 1, 5, 3, 6, 4, 8, 9, 7] ``` 最长递增子序列： ```js [1, 3, 4, 8, 9] [1, 3, 6, 8, 9] [1, 5, 6, 8, 9] [2, 3, 4, 8, 9] [2, 3, 6, 8, 9] [2, 5, 6, 8, 9] ``` 可以看出，即便是最长递增子序列，仍然是可以有多个的。在开发中，不同的算法可能拿到不一样的结果，不过一般拿到其中一个最长递增子序列即可。 实际意义 - 股票趋势分析 - 手写识别 - 文本编辑和版本控制 - .... **暴力法** 暴力法的核心思想是：找到所有的递增子序列，然后从中找到长度最长的那一个。 ```js function getSequence(arr) { let maxLength = 0; // 记录最长递增子序列的长度 let longetSeq = []; // 记录最长递增子序列 /** * * @param {*} index 列表的下标 * @param {*} subSeq 当前递增子序列 */ function findSubsequence(index, subSeq) { let currentNum = arr[index]; // 当前元素 // 先把之前的递增子序列展开，再加上当前元素 let newSeq = [...subSeq, currentNum]; // 新的递增子序列 // 遍历下标之后的内容 for (let i = index + 1; i < arr.length; i++) { // 遍历当前下标之后的元素时，发现有比当前元素大的元素 if (arr[i] > currentNum) { findSubsequence(i, newSeq); } } // 每一次递归结束后，就会得到一个新的递增子序列 // 相当于找到了所有的递增子序列 // console.log("newSeq:", newSeq); if (newSeq.length > maxLength) { maxLength = newSeq.length; longetSeq = newSeq; } } for (let i = 0; i < arr.length; i++) { findSubsequence(i, []); } return longetSeq; } const list = [2, 1, 5, 3, 6, 4, 8, 9, 7]; const result = getSequence(list); console.log(result); // [2, 5, 6, 8, 9] ``` **动态规划** 动态规划（Dynamic Programming）的核心思想是利用问题的**最优子结构**和**重叠子问题**特性，将复杂问题分解为更小的子问题，并且在解决这些子问题的时候会保存子问题的解，避免重复计算，从而高效地求解原问题。 ```js function getSequence(arr) { let maxLength = 0; // 记录最长递增子序列的长度 let maxSeq = []; // 记录最长递增子序列 let sequences = new Array(arr.length).fill().map(() => []); // console.log(sequences); // 遍历数组 for (let i = 0; i < arr.length; i++) { // 创建一个以当前元素为结尾的递增子序列 let seq = [arr[i]]; // 遍历之前的元素，找到比当前元素小的元素，从而构建递增子序列 for (let j = 0; j < i; j++) { if (arr[j] < arr[i]) { // 把之前存储的序列和当前元素拼接起来 seq = sequences[j].concat(arr[i]); } } // 将当前递增子序列存储起来 sequences[i] = seq; // 更新最大的序列 if (seq.length > maxLength) { maxLength = seq.length; maxSeq = seq; } } // console.log(sequences); return maxSeq; } const list = [2, 1, 5, 3, 6, 4, 8, 9, 7]; const result = getSequence(list); console.log(result); // [ 1, 3, 4, 8, 9 ] ``` **Vue3中的算法** Vue3 中获取最长递增子序列，用到了 **贪心** 和 **二分** 查找。 ```js function getSequence(arr) { // 用于记录每个位置的前驱索引，以便最后重建序列 const p = arr.slice(); // 存储当前找到的最长递增子序列的索引 const result = [0]; // 声明循环变量和辅助变量 let i, j, u, v, c; // 获取输入数组的长度 const len = arr.length; // 遍历输入数组 for (i = 0; i < len; i++) { const arrI = arr[i]; // 忽略值为 0 的元素（Vue源码中的diff算法对0有特定处理） if (arrI !== 0) { // 获取当前最长序列中最后一个元素的索引 j = result[result.length - 1]; // 贪心算法部分：如果当前元素大于当前最长序列的最后一个元素，直接添加 if (arr[j] < arrI) { // 记录当前元素的前驱索引为 j p[i] = j; // 将当前元素的索引添加到 result 中 result.push(i); continue; } // 二分查找部分：在 result 中寻找第一个大于等于 arrI 的元素位置 u = 0; v = result.length - 1; while (u < v) { // 取中间位置 c = ((u + v) / 2) | 0; // 比较中间位置的值与当前值 if (arr[result[c]] < arrI) { // 如果中间值小于当前值，搜索区间缩小到 [c + 1, v] u = c + 1; } else { // 否则，搜索区间缩小到 [u, c] v = c; } } // 如果找到的值大于当前值，进行替换 if (arrI < arr[result[u]]) { // 如果 u 不为 0，记录前驱索引 if (u > 0) { p[i] = result[u - 1]; } // 更新 result 中的位置 u 为当前索引 i result[u] = i; } } } // 重建最长递增子序列 u = result.length; v = result[u - 1]; while (u-- > 0) { // 将索引替换为对应的前驱索引 result[u] = v; v = p[v]; } // 返回最长递增子序列的索引数组 return result; } ``` 追踪流程： 1. 初始化： - `p = [2, 1, 5, 3, 6, 4, 8, 9, 7]` 用于记录每个元素的前驱索引，初始为原数组的副本。 - `result = [0]` 初始化结果数组，开始时只包含第一个元素的索引 0。 2. 遍历数组： - `i = 0, arrI = 2` 第一个元素，索引已在 result 中，继续下一次循环。 - `i = 1, arrI = 1` - `arr[result[result.length - 1]] = arr[0] = 2` - `arrI (1) < 2`，需要二分查找替换位置。 - 二分查找 (u = 0, v = 0)： - `c = 0` - `arr[result[0]] = 2 > arrI (1)` - `v = c = 0` - `arrI (1) < arr[result[u]] (2)`，替换 ` result[0] = 1` - 更新 `result = [1]` - `i = 2, arrI = 5` - `arr[result[result.length - 1]] = arr[1] = 1` - `arrI (5) > 1`，贪心算法：直接添加到 result - `p[2] = 1` - `result.push(2)` - 更新 `result = [1, 2]` - `i = 3, arrI = 3` - `arr[result[result.length - 1]] = arr[2] = 5` - `arrI (3) < 5`，需要二分查找。 - 二分查找 (u = 0, v = 1)： - `c = 0` - `arr[result[0]] = arr[1] = 1 < arrI (3)` - `u = c + 1 = 1` - `arr[result[1]] = arr[2] = 5 > arrI (3)` - `v = c = 1` - `arrI (3) < arr[result[u]] (5)`，替换 `result[1] = 3` - `p[3] = result[0] = 1` - 更新 `result = [1, 3]` - `i = 4, arrI = 6` - `arr[result[result.length - 1]] = arr[3] = 3` - `arrI (6) > 3`，贪心算法：直接添加到 result - `p[4] = 3` - `result.push(4)` - 更新 `result = [1, 3, 4]` - `i = 5, arrI = 4` - `arr[result[result.length - 1]] = arr[4] = 6` - `arrI (4) < 6`，需要二分查找。 - 二分查找 (u = 0, v = 2) ： - `c = 1` - `arr[result[1]] = arr[3] = 3 < arrI (4)` - `u = c + 1 = 2` - `arr[result[2]] = arr[4] = 6 > arrI (4)` - `v = c = 2` - `arrI (4) < arr[result[u]] (6)`，替换 `result[2] = 5` - `p[5] = result[1] = 3` - 更新 `result = [1, 3, 5]` - `i = 6, arrI = 8` - `arr[result[result.length - 1]] = arr[5] = 4` - `arrI (8) > 4`，贪心算法：直接添加到 result - `p[6] = 5` - `result.push(6)` - 更新 `result = [1, 3, 5, 6]` - `i = 7, arrI = 9` - `arr[result[result.length - 1]] = arr[6] = 8` - `arrI (9) > 8`，贪心算法：直接添加到 `result` - `p[7] = 6` - `result.push(7)` - 更新 `result = [1, 3, 5, 6, 7]` - `i = 8, arrI = 7` - `arr[result[result.length - 1]] = arr[7] = 9` - `arrI (7) < 9`，需要二分查找。 - 二分查找 (u = 0, v = 4) ： - `c = 2` - `arr[result[2]] = arr[5] = 4 < arrI (7)` - `u = c + 1 = 3` - `c = 3` - `arr[result[3]] = arr[6] = 8 > arrI (7)` - `v = c = 3` - `arrI (7) < arr[result[u]] (8)`，替换 `result[3] = 8` - `p[8] = result[2] = 5` - 更新 `result = [1, 3, 5, 8, 7]` 3. 重建序列： - `u = result.length = 5` - `v = result[u - 1] = result[4] = 7` - 迭代过程： - `result[4] = v = 7` - `v = p[7] = 6` - `result[3] = v = 6` - `v = p[6] = 5` - `result[2] = v = 5` - `v = p[5] = 3` - `result[1] = v = 3` - `v = p[3] = 1` - `result[0] = v = 1` - `v = p[1]`（`p[1]` 初始为 1） - 最终 `result = [1, 3, 5, 6, 7]` 4. 映射回原数组的值： - `result.map(index => list[index])` 得到 `[1, 3, 4, 8, 9]` - 这是输入数组中的一个最长递增子序列 --- -EOF-