简介
最长递增子序列（Longest Increasing Subsequence，简称 LIS）是指在一个给定的数值序列中找到一个尽可能长的子序列，这个子序列的元素是按升序排列的，但不一定是连续的。这个问题在计算机科学和数学中都有广泛的应用，如生物信息学中的DNA序列分析、数据库查询优化等。
动态规划解法
动态规划是一种常用的解决 LIS 问题的方法。其核心思想是通过维护一个数组来记录到目前为止的最长递增子序列长度，并逐步构建出最终的结果。
步骤详解
- 初始化一个数组
dp，其中dp[i]表示以第i个元素结尾的最长递增子序列的长度。 - 将所有
dp[i]的初始值设为 1，因为每个元素自身可以构成一个长度为 1 的递增子序列。 - 遍历数组中的每一个元素，对于每一个元素
arr[i]，再遍历它之前的所有元素arr[j]，如果arr[j] < arr[i]，则更新dp[i]的值为max(dp[i], dp[j] + 1)。 - 在遍历过程中，维护一个变量
maxLength来记录整个数组中最长递增子序列的长度。 - 遍历结束后，
maxLength即为所求。
示例代码
// www.javascriptcn.com code example
function longestIncreasingSubsequence(arr) {
const n = arr.length;
let dp = new Array(n).fill(1);
let maxLength = 1;
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}
// 测试
const arr = [10, 9, 2, 5, 3, 7, 101, 18];
console.log(longestIncreasingSubsequence(arr)); // 输出: 4贪心算法与二分查找解法
除了动态规划之外，还有另一种效率更高的方法——结合贪心算法与二分查找。
步骤详解
- 创建一个辅助数组
tails，用于存储当前递增子序列的尾部元素。 - 遍历原数组，对于每一个元素，使用二分查找找到
tails中第一个大于等于该元素的位置，然后更新该位置的值。 - 如果找不到这样的位置，则将该元素添加到
tails的末尾。 - 最终，
tails的长度即为最长递增子序列的长度。
示例代码
// www.javascriptcn.com code example
function longestIncreasingSubsequence(arr) {
const tails = [];
for (let num of arr) {
let left = 0, right = tails.length;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (tails[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
if (left === tails.length) {
tails.push(num);
} else {
tails[left] = num;
}
}
return tails.length;
}
// 测试
const arr = [10, 9, 2, 5, 3, 7, 101, 18];
console.log(longestIncreasingSubsequence(arr)); // 输出: 4复杂度分析
- 动态规划：时间复杂度为 O(n^2)，空间复杂度为 O(n)。
- 贪心 + 二分查找：时间复杂度为 O(n log n)，空间复杂度为 O(n)。
这两种方法各有优劣，在不同的场景下选择合适的方法至关重要。动态规划方法更易于理解和实现，而贪心算法与二分查找则更适合处理大规模数据的情况。
总结
本章详细介绍了如何使用 JavaScript 实现最长递增子序列算法，包括动态规划和贪心算法与二分查找两种方法。理解这些算法不仅有助于提升算法设计能力，还能帮助解决实际应用中的相关问题。