跳到主要内容

最长递增子序列

最长递增子序列（Longest Increasing Subsequence，简称LIS）

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。

  • leetcode题目是找出最长递增子序列的长度

示例 1：

text
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

思路​

  • 最长递增子序列，可以使用两种解法详细注释
    • 动态规划思路
    • 二分查找思路

动态规划思路​

  • 1、创建一个与输入数组 nums 长度相同的数组 dp，并将其初始化为 1。dp 数组中的每个元素表示以当前元素为结尾的最长递增子序列的长度
  • 2、使用两个指针，外层指针 i 遍历整个数组，内层指针 j 在 0 到 i 的范围内寻找比当前元素小的数字。
  • 3、如果找到一个比当前元素小的数字 nums[j]，更新 dp[i] 为 dp[j] + 1，表示以当前元素结尾的最长递增子序列长度为 dp[j] + 1。
  • 4、遍历完整个数组后，得到的最长递增子序列的长度即为 dp 数组中的最大值
js
function lengthOfLIS(nums) {
  // 获取数组的长度，并检查如果数组长度为 0，则直接返回 0
  const n = nums.length;
  if (n === 0) return 0;

  /**
   * 创建长度n的数组，并将其中的每个元素初始化为 1
   * 数组 dp 用于存储每个位置上的最长递增子序列的长度。
   * 将 dp 数组初始化为 1 的目的是为了确保每个元素自身都可以被视为长度为1的递增子序列
   */
  const dp = new Array(n).fill(1);
  let maxLen = 1;

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        // 更新来寻找更长的递增子序列。
        dp[i] = Math.max(dp[i], dp[j] + 1);
        maxLen = Math.max(maxLen, dp[i]);
      }
    }
  }

  return maxLen;
}