算法图解：如何理解最长递增子序列算法？

一、介绍

本文将以通俗易懂的方式介绍最长递增子序列算法，并提供 JavaScript 代码演示，旨在帮助初学者理解该算法。

最长递增子序列（Longest Increasing Subsequence，简称 LIS）是一种经典的动态规划算法，用于寻找给定序列中最长的严格递增子序列的长度。

二、算法描述

最长递增子序列算法用于寻找一个序列中最长的递增子序列，即按顺序递增且长度最长的子序列。步骤如下：

1. 创建一个数组 dp，其中 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。
2. 初始化 dp 数组，将每个元素的长度都设为 1。
3. 遍历数组，对于每个元素 arr[i]，再遍历其之前的所有元素 arr[j]（j < i），如果 arr[i] > arr[j]，则更新 dp[i] = Math.max(dp[i], dp[j] + 1)。
4. 最后找出 dp 数组中的最大值，即为最长递增子序列的长度。

三、过程图解

假设我们有一个数组 [10, 9, 2, 5, 3, 7, 101, 18]，接下来我们将通过图解的方式来说明算法的执行过程。

1. 初始状态，dp 数组为：[1, 1, 1, 1, 1, 1, 1, 1]。

2. 下标 i 指向元素 9，此时下标 j 指向元素 10，由于元素 10 大于元素 9，因此 dp 数组无变化。

3. 下标 i 指向元素 2，此时下标 j 遍历元素 2 之前的元素，由于元素 10 和元素 9 都比元素 2 大，因此 dp 数组无变化。

4. 下标 i 指向元素 5，此时下标 j 遍历元素 5 之前的元素。

由于元素 10 和元素 9 都比元素 5 大，此时 dp 数组无变化。当下标 j 指向元素 2 时，发现元素 2 小于元素 5，因此 dp[3] = Math.max(dp[3], dp[2] + 1)，即 dp[3] = 2，此时 dp 数组更新为：[1, 1, 1, 2, 1, 1, 1, 1]。

5. 下标 i 指向元素 3，此时下标 j 遍历元素 3 之前的元素。

遍历过程中发现，元素 2 小于元素 3，因此 dp[4] = Math.max(dp[4], dp[2] + 1)，即 dp[4] = 2， dp 数组更新为：[1, 1, 1, 2, 2, 1, 1, 1]。

6. 下标 i 指向元素 7，此时下标 j 遍历元素 7 之前的元素。

遍历过程中发现，元素 2 小于元素 7，因此 dp[5] = Math.max(dp[5], dp[2] + 1)，即 dp[5] = 2， dp 数组更新为：[1, 1, 1, 2, 2, 1, 1, 1]。

下标 j 继续往后遍历，当 j 指向元素 5 时，由于元素 5 小于元素 7，因此 dp[5] = Math.max(dp[5], dp[3] + 1)，即 dp[5] = 3， dp 数组更新为：[1, 1, 1, 2, 3, 1, 1, 1]。

下标 j 继续往后遍历，当 j 指向元素 3 时，由于元素 3 小于元素 7，因此 dp[5] = Math.max(dp[5], dp[4] + 1)，即 dp[5] = 3， dp 数组无变化。此时下标 j 遍历结束，dp 数组为：[1, 1, 1, 2, 2, 3, 1, 1]。

7. 下标 i 指向元素 101，此时下标 j 遍历元素 101 之前的元素，根据上述的步骤，本次遍历结束后，dp 数组更新为：[1, 1, 1, 2, 2, 3, 4, 1]。

8. 下标 i 指向元素 18，此时下标 j 遍历元素 18 之前的元素，根据上述的步骤，本次遍历结束后，dp 数组更新为：[1, 1, 1, 2, 2, 3, 4, 4]。

9. 至此，整个遍历过程结束，dp 数组为：[1, 1, 1, 2, 2, 3, 4, 4]，最长递增子序列的长度为 4。

四、代码演示

下面是使用 JavaScript 实现的最长递增子序列算法的代码演示：

function lengthOfLIS(nums) {
    const n = nums.length;
    const dp = Array(n).fill(1);
    const prevIndex = Array(n).fill(-1); // 用于记录最长递增子序列中每个元素的前一个元素索引
    let maxLen = 1;
    let endIndex = 0; // 记录最长递增子序列的结束索引
    
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                prevIndex[i] = j; // 更新前一个元素索引
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            endIndex = i; // 更新最长递增子序列的结束索引
        }
    }
    
    // 构造最长递增子序列
    const longestIncreasingSubsequence = [];
    let currentIndex = endIndex;
    while (currentIndex !== -1) {
        longestIncreasingSubsequence.unshift(nums[currentIndex]);
        currentIndex = prevIndex[currentIndex];
    }
    
    console.log("最长递增子序列为：" + longestIncreasingSubsequence);
    
    return maxLen;
}

// 示例
const nums = [10, 9, 2, 5, 3, 7, 101, 18];
console.log(lengthOfLIS(nums)); // 输出 4，同时输出最长递增子序列为：[2, 3, 7, 101]

在这个示例中，除了计算最长递增子序列的长度外，我们还通过 prevIndex 数组记录了每个元素在最长递增子序列中的前一个元素的索引，然后根据这些信息构造出了最长递增子序列，并进行了输出。

五、总结

最长递增子序列算法是一种常用的序列处理算法，在前端开发中有着广泛的应用，例如 Vue3 中的 Diff 算法就使用了最长递增子序列算法来优化性能。通过本文的介绍和 JavaScript 代码演示，相信你已经对该算法有了初步的理解。希望这篇文章能够帮助你更好地掌握面向对象编程中的最长递增子序列算法！

原文链接：https://juejin.cn/post/7342349357386694682 作者：Y_d