GESP 七级 · GESP 202503 C++ 七级 第 10 题

给定一个整数数组 nums，找到其中最长的严格上升子序列的长度。子序列是指从原数组中删除一些元素（或不删除）后，剩余元素保持原有顺序的序列。下面的程序横线处应该填入的是（ ）

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

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    vector<int> dp(n, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                ___________________
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    int result = lengthOfLIS(nums);
    cout << result << endl;

    return 0;
}

根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。

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

【考点】动态规划｜递推状态转移｜最长上升子序列

解题思维：dp[i] 定义为以第 i 个元素结尾的最长上升子序列长度。初始化 dp 全为 1（每个元素自身构成长度为 1 的序列）。外层 i 枚举当前位置，内层 j 枚举所有能接在 nums[j] 后面的前驱，当 nums[i] > nums[j] 时，i 可以接在 j 后面，以 i 结尾的序列长度至少为 dp[j] + 1。因此必须用 max 更新：dp[i] = max(dp[i], dp[j] + 1)。这是经典 DP 通法：先定义状态，再写转移方程，最后取全局最优。

陷阱拆解：A 只拷贝了 dp[j]，少了关键的 +1，相当于没把 nums[i] 算进序列里；B 里 dp[i+1] 还没算出来就拿来比较，逻辑颠倒；C 减 1 更是南辕北辙，上升子序列长度只会增加不会减少。最阴险的是 D 乍看正确，但它把 dp[i] 当成可被 dp[j] 覆盖的初值，而 dp[i] 其实已经初始化为 1，再用 max 保留旧值、更新新值才是对的——只背"max 更新"而不懂状态含义，就会误选 A。

反命题思维：若把条件改成 nums[i] >= nums[j]，就变成最长非递减子序列，D 依然成立但语义变了；若改成找最长下降子序列，只需反转比较符号，dp 更新逻辑不变，这正体现了 DP 转移的通用性。下次刷到这类题，先别急着填，自问"这个状态到底代表什么、转移时为什么加 1"，再动手。