LIS 最长递增子序列

✏️ 输入数据

序列（逗号分隔）：

📖 递推方法详解

问题定义：
给定一个无序整数序列 nums[0..n-1]，找到最长严格递增子序列的长度。
子序列不要求连续，但必须保持原顺序。

核心思想：
定义 dp[i] = 以 nums[i] 结尾的最长递增子序列的长度。
那么最终答案 = max(dp[0], dp[1], ..., dp[n-1])

递推公式：

dp[i] = max(1, max(dp[j] + 1) for all j < i if nums[j] < nums[i])

初始化：每个元素自身就是一个长度为 1 的子序列 → dp[i] = 1
递推：对于每个 i，遍历所有 j < i，如果 nums[j] < nums[i]（严格递增），就尝试将 nums[i] 接到以 nums[j] 结尾的子序列后面：dp[i] = max(dp[i], dp[j] + 1)
前驱记录：用 prev[i] 记录 dp[i] 是从哪个 j 转移来的，用于重构 LIS 序列

为什么是 O(n²)：
外层循环遍历 i = 0 → n-1，内层循环遍历 j = 0 → i-1，
比较次数 ≈ n(n-1)/2 = O(n²)。
（注：另有 O(n log n) 的二分优化版本，但不是本文重点）

💻 C++ 核心代码

#include <vector>
#include <algorithm>
using namespace std;

// 返回 LIS 的长度和序列
pair<int, vector<int>> lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return {0, {}};

    // dp[i]: 以 nums[i] 结尾的 LIS 长度
    vector<int> dp(n, 1);

    // prev[i]: 前驱下标，用于回溯 LIS 序列
    vector<int> prev(n, -1);

    int maxLen = 1;
    int maxIdx = 0;

    // 外层: 遍历每个位置 i
    for (int i = 0; i < n; i++) {
        // 内层: 遍历 i 之前的所有位置 j
        for (int j = 0; j < i; j++) {
            // 只有 nums[j] < nums[i] 才能形成递增
            if (nums[j] < nums[i]) {
                // 尝试将 nums[i] 接到以 nums[j] 结尾的序列后面
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;     // 记录从 j 转移来
                }
            }
        }
        // 更新全局最大值
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            maxIdx = i;
        }
    }

    // 回溯重构 LIS 序列
    vector<int> lis;
    for (int cur = maxIdx; cur != -1; cur = prev[cur]) {
        lis.push_back(nums[cur]);
    }
    reverse(lis.begin(), lis.end());  // 逆序得到正序

    return {maxLen, lis};
}

📈 结果

原始序列

—

最长递增子序列长度

—

LIS 序列

—

📋 DP 表详解

每行对应 nums[i]，单元格 (i, j) 表示 j<i 时 nums[j] < nums[i] 的判断结果。
黄色 = 满足 nums[j] < nums[i]，显示 dp[j]+1；绿色 = 全局最大 dp 值。

🔍 详细推导步骤

🎥 视频演示

抖音视频讲解 —— LIS 最长递增子序列（DP 动态规划 O(n²) 和 O(n log n) 两种方法）

🔗 点击观看：https://v.douyin.com/phETHVgSmzc/