300. 最长递增子序列（中等）

Blind 75 › 300. 最长递增子序列（中等） （第 10 章）
文章工具

题目

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

子序列是从原数组中删除若干元素（也可以一个都不删）后，保持剩余元素相对顺序得到的序列；注意“子序列”不要求连续。

自造示例：nums = [4, 10, 4, 5, 7, 9] → 4。一条最长递增子序列是 [4, 5, 7, 9]（对应下标 0、3、4、5），所以答案是 4。

再比如 nums = [7, 7, 7] → 1：相等元素不能构成“严格递增”，每个单元素自己就是一段。

约束：1 ≤ n ≤ 2500；-104 ≤ nums[i] ≤ 104。进阶目标：能否把时间复杂度降到 O(n log n)。

思路

一句话：设 dp[i] = 以 nums[i] 结尾的最长严格递增子序列长度，最后返回 max(dp)。

先想最直白的：把所有子序列都列出来再选最长。数组有 2n 个子序列，n 最大 2500，指数级完全不可行；即使写「选 / 不选」的递归，分支规模也不会变小。

关键观察：一个递增子序列最后一定落在某个下标 i。如果固定结尾是 nums[i]，那它前面的部分必然是一个以 j < i 结尾、且满足 nums[j] < nums[i] 的递增子序列。于是只要算出所有 dp[j]，就能推出 dp[i]：

  • 转移：dp[i] = max(1, 1 + dp[j])，其中 j < i 且 nums[j] < nums[i]。
  • 边界：每个元素自己都能构成长度 1 的子序列，所以 dp[i] 初始为 1。

这就是一维动态规划：从左到右填 dp，每个位置枚举它所有可能的前驱即可。

解法

  1. 初始化 dp 数组，每个位置为 1，并用 result 记录全局最大，初值为 1。
  2. 外层枚举结尾 i，内层枚举前驱 j < i。
  3. 若 nums[j] < nums[i]，尝试把 nums[i] 接在 j 后面：dp[i] = max(dp[i], dp[j] + 1)。
  4. 每一步更新 result = max(result, dp[i])，最后返回 result。

以 [4, 10, 4, 5, 7, 9] 为例逐步填表：

inums[i]可接在哪些 j 后面dp[i]
04无1
1100（4<10）2
24无（前面没有更小）1
350、2（4<5）2
470、2、3（5<7）3
590、2、3、4（7<9）4

结果 max(dp) = 4。此例中 dp 的最后一个位置恰好是答案，但这并非必然——最长子序列不必以最后一个元素结尾。

下图把上面 4 个步骤串成流程，并逐步演示：

300. 最长递增子序列（中等） 解法步骤流程图
图① 解法步骤流程图（共 4 步）。
300. 最长递增子序列（中等） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;

        vector<int> dp(n, 1);   // 以 nums[i] 结尾的最长长度，至少是自身
        int result = 1;

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {           // 严格递增
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            result = max(result, dp[i]);           // 答案未必在最后一个位置
        }
        return result;
    }
};

Python

Python 3 示例