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

给定一个整数数组 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]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    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;
}

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】动态规划｜时间复杂度分析｜子序列定义

：GESP 七级 C++ 大纲中“动态规划”模块的递推思想落地题，命题人特意用 O(n²) 解法卡住只会贪心或公式的考生——他们往往忽略“子序列必须保持原顺序”这一约束，误以为可以重排。

核心思路是定义 dp[i] 为以 nums[i] 结尾的最长上升子序列长度。外层循环枚举每个位置 i，内层循环找所有比它小的前驱 j，用 max(dp[j] + 1) 更新 dp[i]。这是标准的“状态转移”模型，嵌套两层循环必然导致 O(n²) 时间复杂度。

选项 B 和 C 明显不可能：LIS 必须遍历所有元素，O(n) 或 O(log n) 都无法完成。选项 D 看似有道理，因为 LIS 确实存在 O(n log n) 的贪心+二分解法，但本题代码用的是朴素 DP，没有用到二分优化，所以 D 是命题人设的“高级陷阱”——考生若只背结论"LIS 是 O(n log n)"，就会误选 D。

若把 nums[i] > nums[j] 改成 nums[i] >= nums[j] 就变成了最长非降子序列，复杂度不变；若改成 dp[i] = min(dp[i], dp[j] + 1) 就变成了最长下降子序列，同样 O(n²)。反推可知，任何只改变比较符号或方向，都无法降低到 O(n log n)，除非引入二分查找结构。