338 lines
9.4 KiB
Markdown
338 lines
9.4 KiB
Markdown
# 最长递增子序列
|
||
|
||
**基本介绍**
|
||
|
||
最长递增子序列（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- |