最长上升子序列——找出连续上升的数字队伍

找出最长的“递增”队伍——最长上升子序列（LIS）

想象一下，老师让全班同学按身高打乱站成一排，然后想看看：从这排同学中挑出一些人，保持原来的顺序（不能交换位置），让后面的人严格比前面的人高，这样能挑出的最长队伍有多长？比如身高数组 [3,1,4,2,5]，可以挑出 [1,2,5] 或 [1,4,5]，长度都是3。这个问题在生活中很常见：比如考试分数排名中，找出一次比一次进步的科目顺序；或者游戏里角色等级依次上升的任务链。在计算机科学里，它叫“最长上升子序列”（Longest Increasing Subsequence, LIS）。

子序列和子数组不同：子数组必须是连续的，比如 [3,1,4]；而子序列可以不连续，只要保持原顺序就行。所以这里找的是不连续但严格递增的最长队伍。

动态规划思路——一步步搭积木

我们用一个数组 dp 来记录每个“结尾”能组成的最长递增队伍长度。
定义：dp[i] 表示以数字 nums[i] 作为最后一个人时，最长递增子序列的长度。
比如对于身高数组 [3,1,4,2,5]，dp[0] 表示以身高3结尾的最长递增子序列，3前面没人，所以长度就是1（只有自己）。

转移方程：对于每个 i，我们回头看它前面所有的数字 nums[j]（j < i）。如果 nums[j] < nums[i]（前面的人比当前矮），就可以把当前数字接到以 nums[j] 结尾的队伍后面，形成一条更长的队伍，长度为 dp[j] + 1。我们取所有可能接法中的最大值：
dp[i] = max(dp[i], dp[j] + 1)
注意：如果前面没有可以接的数字，那 dp[i] 就保持初始值1（自己一个人）。

初始化：每个 dp[i] 都至少为1，因为每个数字自己可以独立成为一个长度为1的递增子序列。

最终答案：整个数组的最长上升子序列长度，就是所有 dp[i] 中的最大值。

举个例子：手把手算一遍

假设身高数组 nums = {3, 1, 4, 2, 5}，一共5个人。

1. 初始化 dp = [1, 1, 1, 1, 1]
2. 处理 i = 0（身高3）：前面没人，dp[0] 保持1。
3. 处理 i = 1（身高1）：看前面 j=0，nums[0]=3 并不小于1，所以不能接，dp[1] 保持1。
4. 处理 i = 2（身高4）：
   • j=0: 3 < 4 成立，dp[2] = max(1, 1+1)=2
   • j=1: 1 < 4 成立，dp[2] = max(2, 1+1)=2（还是2） 所以 dp[2]=2，表示以4结尾的最长序列是 [3,4] 或 [1,4]。
5. 处理 i = 3（身高2）：
   • j=0: 3 < 2? 不成立
   • j=1: 1 < 2 成立，dp[3] = max(1, 1+1)=2
   • j=2: 4 < 2? 不成立 所以 dp[3]=2，序列是 [1,2]。
6. 处理 i = 4（身高5）：
   • j=0: 3 < 5 => dp[4] = max(1, 1+1)=2
   • j=1: 1 < 5 => dp[4] = max(2, 1+1)=2
   • j=2: 4 < 5 => dp[4] = max(2, 2+1)=3
   • j=3: 2 < 5 => dp[4] = max(3, 2+1)=3 所以 dp[4]=3，对应序列 [1,4,5] 或 [1,2,5]。

最终 dp = [1,1,2,2,3]，最大值是3，所以最长上升子序列长度为3。

完整代码（含详细注释）

#include <iostream>
#include <vector>
#include <algorithm>   // 用到了max函数
using namespace std;

int main() {
    vector<int> nums = {3, 1, 4, 2, 5};   // 身高序列
    int n = nums.size();                  // 序列长度
    vector<int> dp(n, 1);                 // dp[i]：以第i个数结尾的最长上升子序列长度，初始为1

    // 动态规划：两层循环
    for (int i = 0; i < n; i++) {        // i：当前考虑的数
        for (int j = 0; j < i; j++) {    // j：前面的数
            if (nums[j] < nums[i]) {     // 只有前面的数更小，才能接在后面
                dp[i] = max(dp[i], dp[j] + 1);  // 更新dp[i]
            }
        }
    }

    // 找出所有dp[i]的最大值
    int ans = 0;                         // 最终答案
    for (int i = 0; i < n; i++) {
        ans = max(ans, dp[i]);
    }

    cout << "最长上升子序列的长度是: " << ans << endl;
    return 0;
}

运行这个程序，输出：最长上升子序列的长度是: 3。

新手容易犯的3个错误

1. 忘记初始化 dp[i]=1
   如果不初始化，dp 默认全是0，那么 dp[i] = max(dp[i], dp[j]+1) 时，即使前面有比它小的数，dp[i] 也只会变成1，但万一后面还有可接的，就会丢失长度。一定要先给每个位置赋值为1。

2. 把子序列当成子数组
   有些同学会只比较相邻两个数，比如看到 [3,1,2]，就认为最长是2（因为3和1不递增，1和2递增）。但正确的最长上升子序列是 [1,2] 或者 [3]，长度为2。所以一定要看所有前面的数，不只是相邻的。

3. 条件写成 nums[j] <= nums[i]
   题目要求严格递增，如果允许相等（<=），比如 [2,2,2] 的答案就会变成3（把每个都接上去），但实际上严格递增要求后面的必须比前面的大，相等不能接。

相关知识点推荐

• 最长下降子序列：把判断条件改成 nums[j] > nums[i] 就行，逻辑完全一样。
• 最长公共子序列 (LCS)：求两个序列的公共子序列的最长长度，也是动态规划经典问题。
• 二分优化：上面双层循环的时间复杂度是 O(n²)，当 n 很大（比如10万）时会超时。用“耐心排序”思想，结合二分查找可以将复杂度降到 O(n log n)，有兴趣的同学可以查查“贪心+二分”优化方法。

掌握了最长上升子序列，你就学会了动态规划中一种非常实用的“以结尾分类”的思考方式。下次遇到类似“按顺序组合”的问题，试试用 dp[i] 来记录以某个元素为结尾的最优值吧！