题目链接 · 灵神原题解（署名来源）

视频讲解

请看 最长递增子序列【基础算法精讲 20】，制作不易，欢迎点赞关注~

方法一：记忆化搜索

$\mathit{\text{dfs}}(i)$ 表示以 $\mathit{\text{nums}}[i]$ 结尾的最长递增子序列（LIS）的长度。

枚举子序列的倒数第二个数的下标是 $j$，如果 $\mathit{\text{nums}}[j]<\mathit{\text{nums}}[i]$，那么有

$$\mathit{\text{dfs}}(i)=\mathit{\text{dfs}}(j)+1$$

取最大值。

注意 $\mathit{\text{nums}}[i]$ 可以单独形成一个长为 $1$ 的子序列。

答疑

问：什么样的题目适合「选或不选」，什么样的题目适合「枚举选哪个」？

答：我分成两类问题：

• 相邻无关子序列问题（比如 0-1 背包），适合「选或不选」。每个元素互相独立，只需依次考虑每个元素选或不选。
• 相邻相关子序列问题（比如本题），适合「枚举选哪个」。我们需要知道子序列中的相邻两个数的关系。对于本题来说，枚举 $\mathit{\text{nums}}[i]$ 必选，然后枚举前一个必选的数，方便比大小。如果硬要用「选或不选」，需要额外记录上一个选的数的下标，算法总体的空间复杂度为 $\mathcal{O}(n^2)$，而枚举选哪个只需要 $\mathcal{O}(n)$ 的空间。

Python 解法1

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            res = 0
            for j in range(i):
                if nums[j] < nums[i]:
                    res = max(res, dfs(j))
            return res + 1  # 加一提到循环外面

        return max(dfs(i) for i in range(len(nums)))

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> memo(n);

        auto dfs = [&](this auto&& dfs, int i) -> int {
            int& res = memo[i]; // 注意这里是引用
            if (res > 0) { // 之前计算过
                return res;
            }
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    res = max(res, dfs(j));
                }
            }
            res++; // 加一提到循环外面
            return res;
        };

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = max(ans, dfs(i));
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n^2)$，其中 $n$ 为 $\mathit{\text{nums}}$ 的长度。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题中状态个数等于 $\mathcal{O}(n)$，单个状态的计算时间为 $\mathcal{O}(n)$，所以动态规划的时间复杂度为 $\mathcal{O}(n^2)$。
• 空间复杂度：$\mathcal{O}(n)$。保存多少状态，就需要多少空间。

方法二：递推

同记忆化搜索，$f[i]$ 表示以 $\mathit{\text{nums}}[i]$ 结尾的最长递增子序列（LIS）的长度。

Python 解法3

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        f = [0] * len(nums)
        for i, x in enumerate(nums):
            for j, y in enumerate(nums[:i]):
                if x > y:
                    f[i] = max(f[i], f[j])
            f[i] += 1
        return max(f)

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        for (int i = 0; i < n; i++) {
            f[i] = 0;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    f[i] = max(f[i], f[j]);
                }
            }
            f[i]++;
        }
        return ranges::max(f);
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n^2)$，其中 $n$ 为 $\mathit{\text{nums}}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

方法三：贪心 + 二分查找

注：方法三本质是对上述 DP 做法的优化，也算 DP 做法。

假设 $f[3]$ 和 $f[4]$ 的值都等于 $2$，且 $\mathit{\text{nums}}[3]=99999$，$\mathit{\text{nums}}[4]=9$。

我们现在要计算 $f[5]$。想一想，谁更容易满足上面代码中的 if (nums[j] < nums[i])？这里 $i=5$，$j=3$ 或者 $4$。

$\mathit{\text{nums}}[4]$ 更小，更容易满足 if (nums[j] < nums[i])。更大的 $\mathit{\text{nums}}[3]$ 虽然也可能满足条件，但由于 $f[3]=f[4]$，在更新 $f[5]$ 时，二者的效果是一样的，所以 $\mathit{\text{nums}}[3]$ 是个无用数据。换句话说，对于相同的 $f$ 值，我们只需保留更小的 $\mathit{\text{nums}}[i]$。

注：这个「去掉无用数据」的想法和单调栈是一样的。见 单调栈【基础算法精讲 26】。

因此，定义 $g[i]$ 表示 $f[j]=i+1$ 时，$\mathit{\text{nums}}[j]$ 的最小值。也就是长为 $i+1$ 的上升子序列的末尾元素的最小值。这里 $+1$ 是因为 $f[j]$ 至少是 $1$，$g[0]$ 对应的不是 $f[j]=0$，而是 $f[j]=1$。

关于 $g$ 数组的性质，请看 最长递增子序列【基础算法精讲 20】。

写法一：额外空间

Python 解法5

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        g = []
        for x in nums:
            j = bisect_left(g, x)
            if j == len(g):  # >=x 的 g[j] 不存在
                g.append(x)
            else:
                g[j] = x
        return len(g)

C++ 解法5

// C++ 版待补充

C++ 解法6

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> g;
        for (int x : nums) {
            auto it = ranges::lower_bound(g, x);
            if (it == g.end()) {
                g.push_back(x); // >=x 的 g[j] 不存在
            } else {
                *it = x;
            }
        }
        return g.size();
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 为 $\mathit{\text{nums}}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

写法二：原地修改

直接把 $g$ 填入 $\mathit{\text{nums}}$ 中。

Python 解法7

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        ng = 0  # g 的长度
        for x in nums:
            j = bisect_left(nums, x, 0, ng)
            nums[j] = x
            if j == ng:  # >=x 的 g[j] 不存在
                ng += 1 
        return ng

C++ 解法7

// C++ 版待补充

C++ 解法8

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        auto end = nums.begin();
        for (int x : nums) {
            auto it = lower_bound(nums.begin(), end, x);
            *it = x;
            if (it == end) { // >=x 的 g[j] 不存在
                ++end;
            }
        }
        return end - nums.begin();
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 为 $\mathit{\text{nums}}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

附：返回一个具体的 LIS

Python 解法9

class Solution:
    def findOneLIS(self, nums: List[int]) -> List[int]:
        if not nums:
            return []

        n = len(nums)
        g = []  # 不仅记录值，还记录值对应的下标
        last = [-1] * n

        for i, x in enumerate(nums):
            j = bisect_left(g, x, key=lambda t: t[0])
            if j > 0:
                last[i] = g[j - 1][1]  # 记录 nums[i] 添加到了哪个数的末尾
            if j < len(g):
                g[j] = (x, i)  # 额外保存下标
            else:
                g.append((x, i))

        lis = []
        i = g[-1][1]  # LIS 的最后一个数是 nums[g[-1][1]]
        while i >= 0:
            lis.append(nums[i])
            i = last[i]  # 顺着 last 倒着找上一个数
        lis.reverse()
        return lis

C++ 解法9

// C++ 版待补充

C++ 解法10

class Solution {
public:
    vector<int> findOneLis(vector<int>& nums) {
        if (nums.empty()) {
            return {};
        }

        int n = nums.size();
        vector<pair<int, int>> g; // 不仅记录值，还记录值对应的下标
        vector<int> last(n, -1);

        for (int i = 0; i < n; i++) {
            int x = nums[i];
            int j = ranges::lower_bound(g, x, {}, &pair<int, int>::first) - g.begin();
            if (j > 0) {
                last[i] = g[j - 1].second; // 记录 nums[i] 添加到了哪个数的末尾
            }
            if (j < g.size()) {
                g[j] = {x, i}; // 额外保存下标
            } else {
                g.emplace_back(x, i);
            }
        }

        vector<int> lis;
        // LIS 的最后一个数是 nums[g.back().second]，顺着 last 倒着找上一个数
        for (int i = g.back().second; i >= 0; i = last[i]) {
            lis.push_back(nums[i]);
        }
        ranges::reverse(lis);
        return lis;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 为 $\mathit{\text{nums}}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

专题训练

见下面动态规划题单的「§4.2 最长递增子序列（LIS）」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府