如何在JavaScript中实现最长递增子序列(LIS)

在计算机科学中，寻找一个序列中的最长递增子序列（LIS）是一个常见的问题。这个问题不仅在算法竞赛中经常出现，也是许多实际应用的基础，例如股票交易策略、基因序列比对等。本文将详细介绍如何使用动态规划方法在JavaScript中实现LIS。

1. 动态规划概述

动态规划是一种通过将复杂问题分解为一系列较简单的子问题来解决问题的方法。在求解最长递增子序列时，我们可以通过构建一个数组来存储当前为止能找到的最长递增子序列长度。

2. 动态规划步骤

2.1 初始化状态

我们定义一个数组 dp，其中 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。初始化所有元素为 1，因为每个单独的元素本身就是一个递增子序列。

function findLongestIncreasingSubsequence(arr) {
    const dp = new Array(arr.length).fill(1);
}

2.2 遍历并计算

遍历数组，对于每个元素 arr[i]，检查前面的所有元素 arr[j]（j < i），如果 arr[j] < arr[i]，则更新 dp[i] 的值为 max(dp[i], dp[j] + 1)。这一步骤确保了我们总是使用前面的递增子序列来构造更长的递增子序列。

for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
        if (arr[j] < arr[i]) {
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
}

2.3 找到最长递增子序列的长度

在完成上述步骤后，dp 数组中的最大值即为最长递增子序列的长度。

const maxLisLength = Math.max(...dp);

2.4 重建最长递增子序列

为了找到具体的最长递增子序列，我们需要一个额外的过程来追踪哪些元素构成了这个序列。这通常涉及逆向追踪 dp 数组和原始数组 arr。

function reconstructLis(arr, dp) {
    let n = arr.length;
    let lis = [];
    let currentLength = dp[n - 1];
    
    for (let i = n - 1; i >= 0; i--) {
        if (dp[i] === currentLength && lis.length !== n) {
            lis.push(arr[i]);
            currentLength--;
        }
    }
    
    return lis.reverse();
}

2.5 整合完整函数

将所有步骤整合到一个完整的函数中：

function findLongestIncreasingSubsequence(arr) {
    const dp = new Array(arr.length).fill(1);
    for (let i = 1; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    
    const maxLisLength = Math.max(...dp);
    const lis = reconstructLis(arr, dp);
    
    return { length: maxLisLength, sequence: lis };
}

3. 示例

假设我们有一个数组 [10, 9, 2, 5, 3, 7, 101, 18]，我们可以调用上述函数来找到最长递增子序列：

const result = findLongestIncreasingSubsequence([10, 9, 2, 5, 3, 7, 101, 18]);
console.log(result); // 输出 { length: 4, sequence: [2, 3, 7, 101] }

这段代码不仅展示了如何在JavaScript中实现LIS，还提供了完整且易于理解的解决方案，包括找到序列的长度和具体的序列。