GESP 八级 · GESP 202506 C++ 八级 第 13 题

下面 LIS 函数试图求出最长上升子序列的长度，横线处应该填入的是（ ）。

int max(int a, int b) {
    return (a > b) ? a : b;
}
int LIS(vector<int> & nums) {
    int n = nums.size();
    if (n == 0)
        return 0;
    vector<int> dp(n, 1);
    int maxLen = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (nums[j] < nums[i])
                ________;  // 在此处填入选项
        maxLen = max(maxLen, dp[i]);
    }
    return maxLen;
}

STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。

填空时注意语法完整性：分号、括号匹配、函数参数类型和个数、返回值类型。

【考点】动态规划递推｜最长上升子序列（LIS）

【解题思维】dp[i] 定义以 nums[i] 结尾的 LIS 长度，初始为 1（自身成列）。内层循环枚举所有 j<i，当 nums[j]<nums[i] 时，nums[i] 能接在 j 后面构成更长子序列，新长度为 dp[j]+1。由于 dp[i] 要保留所有可能接法中的最优值，必须用 max(dp[i], dp[j]+1) 更新，即 D 选项。

【陷阱拆解】A、B 把 dp[j] 当目标去更新，但 dp[j] 是历史状态，不该被当前 i 影响；C 写成 dp[i]+1 却与 dp[j] 比，逻辑完全反了。最阴险的是 C：它只改了一个 +1 的位置，让 dp[i] 先自增再比较，看似对称实则破坏 DP 语义。只有 D 正确：用 dp[j]+1 去更新 dp[i]，且保留原来的 dp[i] 作为备选。

【反命题思维】若改成最长非增子序列，条件变为 nums[j]>=nums[i]，选项 D 依然适用（只是比较方向变了）。刷 LIS 类题，先问自己"状态定义是什么？转移方向对吗？"