【LeetCode精选TOP面试题】300-最长递增子序列

LeetCode 原题链接

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

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

动态规划解法

思路

dp[i] 表示以 i 结尾的最大递增子序列长度。

dp[i] 取决于 dp[i - 1] 的子序列是否要加入 i。

如果加入 i 可以让子序列更长则 dp[i] = dp[i - 1] + 1，否则 dp[i] = dp[i - 1]。

问题是如何判断加入 i 可以让子序列更长？

1. 往前找所有比 i 小的数都可以跟 i 组成更长的递增子序列 dp[i] = dp[j] + 1。
2. 找到所有组合中最大子序列长度作为 dp[i]，即：dp[i] = Math.max(dp[i], dp[j] + 1)。

dp 中的最大值就是 nums 的最大递增子序列长度。

复杂度

• 时间复杂度：O(n^2)。
• 空间复杂度：O(n)。

代码

var lengthOfLIS = function (nums) {
  const n = nums.length;
  const dp = new Array(n).fill(1);

  for (let i = 1; i < n; i++) {
    for (let j = i - 1; j >= 0; j--) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  return Math.max(...dp);
};

let result = lengthOfLIS([10, 9, 3, 7, 2, 5, 6, 101, 102, 18, 19, 20, 21]);
console.log(result);