GESP 七级 · GESP 202312 C++ 七级 第 3 题

下面代码可以用来求最长上升子序列（LIS）的长度，如果输入是：$5\ 1\ 7\ 3\ 5\ 9$，则输出是（ ）。

int a[2023], f[2023];
int main()
{
    int n, i, j, ans = -1;

    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> a[i];
        f[i] = 1;
    }

    for (i = 1; i <= n; i++)
        for (j = 1; j < i; j++)
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    for (i = 1; i <= n; i++) {
        ans = max(ans, f[i]);
        cout << f[i] << " ";
    }

    cout << ans << endl;
    return 0;
}

这题考的是动态规划里最长上升子序列（LIS）的经典写法，命题人把输出拆成了两行：先一行把每个 f[i] 都打出来，再单独一行输出最终答案 ans。拿到题先别急着算 LIS 长度，要盯着代码最后那个循环——它把 f 数组每个元素都输出了，这才是选对选项的关键线索。

很多同学看到 LIS 就只盯着最终答案 ans=4，忽略了代码里显式打印了中间状态 f[i] 这一行。选项 A 把数字倒序排了，选项 C 像是把子序列本身列出来，选项 D 全是一，都是典型的‘只记结论不看代码’的陷阱。另外数组下标从 1 开始这点容易被忽略，导致算错 f[2] 的值。

【考点】动态规划｜最长上升子序列｜二维嵌套循环

1. 考纲定位

GESP 七级《算法与数据结构》模块，动态规划经典题型。命题人盯住的是考生对「DP 状态含义」的理解——不是背结论，而是看懂代码里每一行在算什么。七级喜欢把「状态转移」和「输出细节」拆开考，这题就是典型：让你算 LIS 长度，但中间多印了一行 f 数组，很多只记「LIS=4」的同学就会掉坑里。