#300.最长递增子序列

LeetCode 原题链接

#1. dp 数组含义

定义一维数组 dp：

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

注意这里的关键是“以 nums[i] 结尾”。

因为子序列不要求连续，所以不能只看相邻元素，而是要看 i 前面的所有位置 j。只要满足：

nums[j] < nums[i]

就说明 nums[i] 可以接在以 nums[j] 结尾的递增子序列后面。

题目要求整个数组中的最长递增子序列长度，所以最终答案是：

Math.max(...dp)

#2. 确定状态转移方程

对于位置 i，需要枚举它前面的每一个位置 j：

0 <= j < i

如果：

nums[j] < nums[i]

说明 nums[i] 可以接在 nums[j] 后面，形成一个更长的递增子序列：

dp[j] + 1

但是满足条件的 j 可能有很多个，我们要选择其中最长的那个，所以状态转移方程是：

dp[i] = Math.max(dp[i], dp[j] + 1);

一句话总结：以 nums[i] 结尾的最长递增子序列，可以由前面某个比它小的 nums[j] 接上 nums[i] 得到。

#3. dp 数组如何初始化

每个位置本身都可以单独组成一个长度为 1 的递增子序列。

所以所有 dp[i] 都初始化为 1：

const dp = new Array(nums.length).fill(1);

例如 nums = [10, 9, 2]，即使没有任何两个数字能组成递增关系，每个数字自己也至少是一个长度为 1 的递增子序列。

如果 nums 是空数组，直接返回 0。

#4. 确定遍历顺序

dp[i] 依赖的是它前面位置的状态 dp[j]，其中：

j < i

所以外层循环 i 必须从前往后遍历。

对于每个 i，内层循环枚举 0 到 i - 1 的所有位置 j：

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

这样在计算 dp[i] 时，所有可能用到的 dp[j] 都已经计算完成。

#5. 举例打印 dp 数组

以 nums = [10, 9, 2, 5, 3, 7] 为例。

初始化：

从左到右遍历：

#i = 0，nums[i] = 10

前面没有元素，dp[0] 保持为 1。

dp = [1, 1, 1, 1, 1, 1]

#i = 1，nums[i] = 9

前面只有 10，但 10 < 9 不成立，不能接在后面。

dp = [1, 1, 1, 1, 1, 1]

#i = 2，nums[i] = 2

前面的 10、9 都比 2 大，不能接在后面。

dp = [1, 1, 1, 1, 1, 1]

#i = 3，nums[i] = 5

2 < 5，所以 5 可以接在 2 后面：

dp[3] = dp[2] + 1 = 2

dp = [1, 1, 1, 2, 1, 1]

#i = 4，nums[i] = 3

2 < 3，所以 3 可以接在 2 后面：

dp[4] = dp[2] + 1 = 2

dp = [1, 1, 1, 2, 2, 1]

#i = 5，nums[i] = 7

2 < 7，可以得到长度 2。

5 < 7，可以得到：

dp[3] + 1 = 3

3 < 7，也可以得到：

dp[4] + 1 = 3

所以：

dp[5] = 3

最终：

dp = [1, 1, 1, 2, 2, 3]

最长递增子序列长度是：

Math.max(...dp) = 3

对应的递增子序列可以是：

[2, 5, 7]

也可以是：

[2, 3, 7]

#6. 代码实现

var lengthOfLIS = function (nums) {
  if (nums.length === 0) return 0;

  const dp = new Array(nums.length).fill(1);

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

  return Math.max(...dp);
};

#复杂度分析

• 时间复杂度：O(n^2)，每个位置 i 都要枚举它前面的所有位置 j。
• 空间复杂度：O(n)，需要一个长度为 n 的 dp 数组。