最长递增子序列
# 最长递增子序列
基本介绍
最长递增子序列（Longest Increasing Subsequence，简称 LIS）是计算机科学中一个经典的算法问题。这看上去是很难的一个词语，遇到这种词，最简单的方法就是拆词，这里可以拆为 3 个词：最长、递增、子序列。
子序列
[1, 2, 3, 4, 5]子序列有多个：
[1, 2, 3] [1, 3] [2, 4, 5]递增
[2, 1, 5, 3, 6, 4, 8, 9, 7]这个子序列里面的元素必须是递增的：
[1, 5] // 子序列，并且是递增的 [1, 3, 6] // 子序列，并且是递增的 [2, 1, 5] // 子序列，但是不是递增的最长
相当于在上面的基础上，有增加了一个条件，需要是最长的、递增的子序列
[2, 1, 5, 3, 6, 4, 8, 9, 7]最长递增子序列：
[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]可以看出，即便是最长递增子序列，仍然是可以有多个的。在开发中，不同的算法可能拿到不一样的结果，不过一般拿到其中一个最长递增子序列即可。
实际意义
- 股票趋势分析
- 手写识别
- 文本编辑和版本控制
- ....
暴力法
暴力法的核心思想是：找到所有的递增子序列，然后从中找到长度最长的那一个。
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）的核心思想是利用问题的最优子结构和重叠子问题特性，将复杂问题分解为更小的子问题，并且在解决这些子问题的时候会保存子问题的解，避免重复计算，从而高效地求解原问题。
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 中获取最长递增子序列，用到了 贪心 和 二分 查找。
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;
}
追踪流程：
初始化：
p = [2, 1, 5, 3, 6, 4, 8, 9, 7]用于记录每个元素的前驱索引，初始为原数组的副本。result = [0]初始化结果数组，开始时只包含第一个元素的索引 0。
遍历数组：
i = 0, arrI = 2第一个元素，索引已在 result 中，继续下一次循环。i = 1, arrI = 1arr[result[result.length - 1]] = arr[0] = 2arrI (1) < 2，需要二分查找替换位置。- 二分查找 (u = 0, v = 0)：
c = 0arr[result[0]] = 2 > arrI (1)v = c = 0
arrI (1) < arr[result[u]] (2)，替换result[0] = 1- 更新
result = [1]
i = 2, arrI = 5arr[result[result.length - 1]] = arr[1] = 1arrI (5) > 1，贪心算法：直接添加到 resultp[2] = 1result.push(2)- 更新
result = [1, 2]
i = 3, arrI = 3arr[result[result.length - 1]] = arr[2] = 5arrI (3) < 5，需要二分查找。- 二分查找 (u = 0, v = 1)：
c = 0arr[result[0]] = arr[1] = 1 < arrI (3)u = c + 1 = 1arr[result[1]] = arr[2] = 5 > arrI (3)v = c = 1
arrI (3) < arr[result[u]] (5)，替换result[1] = 3p[3] = result[0] = 1- 更新
result = [1, 3]
i = 4, arrI = 6arr[result[result.length - 1]] = arr[3] = 3arrI (6) > 3，贪心算法：直接添加到 resultp[4] = 3result.push(4)- 更新
result = [1, 3, 4]
i = 5, arrI = 4arr[result[result.length - 1]] = arr[4] = 6arrI (4) < 6，需要二分查找。- 二分查找 (u = 0, v = 2) ：
c = 1arr[result[1]] = arr[3] = 3 < arrI (4)u = c + 1 = 2arr[result[2]] = arr[4] = 6 > arrI (4)v = c = 2
arrI (4) < arr[result[u]] (6)，替换result[2] = 5p[5] = result[1] = 3- 更新
result = [1, 3, 5]
i = 6, arrI = 8arr[result[result.length - 1]] = arr[5] = 4arrI (8) > 4，贪心算法：直接添加到 resultp[6] = 5result.push(6)- 更新
result = [1, 3, 5, 6]
i = 7, arrI = 9arr[result[result.length - 1]] = arr[6] = 8arrI (9) > 8，贪心算法：直接添加到resultp[7] = 6result.push(7)- 更新
result = [1, 3, 5, 6, 7]
i = 8, arrI = 7arr[result[result.length - 1]] = arr[7] = 9arrI (7) < 9，需要二分查找。- 二分查找 (u = 0, v = 4) ：
c = 2arr[result[2]] = arr[5] = 4 < arrI (7)u = c + 1 = 3c = 3arr[result[3]] = arr[6] = 8 > arrI (7)v = c = 3
arrI (7) < arr[result[u]] (8)，替换result[3] = 8p[8] = result[2] = 5- 更新
result = [1, 3, 5, 8, 7]
重建序列：
u = result.length = 5v = result[u - 1] = result[4] = 7- 迭代过程：
result[4] = v = 7v = p[7] = 6result[3] = v = 6v = p[6] = 5result[2] = v = 5v = p[5] = 3result[1] = v = 3v = p[3] = 1result[0] = v = 1v = p[1]（p[1]初始为 1）
- 最终
result = [1, 3, 5, 6, 7]
映射回原数组的值：
result.map(index => list[index])得到[1, 3, 4, 8, 9]- 这是输入数组中的一个最长递增子序列
-EOF-