最长递增子序列

LeetCode 官方题目链接

题目描述

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

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

示例 1：

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

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

思路拆解

这是一道经典的动态规划题目。

动态规划

1. 定义状态：dp[i] 表示以 nums[i] 结尾 的最长递增子序列的长度。
2. 状态转移方程：
   • 对于每个位置 i，我们需要遍历它前面的所有位置 j（0 <= j < i）。
   • 如果 nums[i] > nums[j]，说明 nums[i] 可以接在 nums[j] 后面形成一个更长的递增子序列。
   • 此时 dp[i] = Math.max(dp[i], dp[j] + 1)。
   • 否则，nums[i] 无法接在 nums[j] 后面，不做处理。
3. 初始条件：
   • 每个元素自身至少可以构成一个长度为 1 的子序列，所以 dp 数组初始化为 1。
4. 返回值：
   • dp 数组中的最大值（因为最长子序列不一定以最后一个元素结尾）。

进阶优化

本题还可以通过 贪心 + 二分查找 的方法将时间复杂度优化到 $O(n \log n)$，但动态规划解法是面试中最基础且必须掌握的。

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    if (nums.length === 0) return 0;
    
    // dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
    // 初始化为 1，因为每个元素本身就是长度为 1 的子序列
    const dp = new Array(nums.length).fill(1);
    let maxLen = 1;

    for (let i = 1; i < nums.length; 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;
};

运行演示

假设 nums = [10, 9, 2, 5, 3, 7, 101, 18]：

1. 初始化 dp 全为 1。
2. i = 1 (9): 比 10 小，不更新。 dp[1]=1
3. i = 2 (2): 比 10, 9 小，不更新。 dp[2]=1
4. i = 3 (5):
   • 5 > 2: dp[3] = max(1, dp[2]+1) = 2
5. i = 4 (3):
   • 3 > 2: dp[4] = max(1, dp[2]+1) = 2
6. i = 5 (7):
   • 7 > 2: dp[5] = 2
   • 7 > 5: dp[5] = max(2, dp[3]+1) = 3
   • 7 > 3: dp[5] = max(3, dp[4]+1) = 3
7. i = 6 (101):
   • ... 接在 7 后面 ... dp[6] = 4
8. i = 7 (18):
   • ... 接在 7 后面 ... dp[7] = 4

最终最大值是 4。

复杂度分析

• 时间复杂度：$O(n^2)$，双重循环。
• 空间复杂度：$O(n)$，需要 dp 数组。