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

下面 LIS 函数试图求出最长上升子序列的长度，其时间复杂度为（ ）。

#define INT_MIN (-1000)
int LIS(vector<int> & nums) {
    int n = nums.size();
    vector<int> tail;
    tail.push_back(INT_MIN);
    for (int i = 0; i < n; i++) {
        int x = nums[i], l = 0, r = tail.size();
        while (l < r) {
            int mid = (l + r) / 2;
            if (tail[mid] < x)
                l = mid + 1;
            else
                r = mid;
        }
        if (r == tail.size())
            tail.push_back(x);
        else
            tail[r] = x;
    }
    return tail.size() - 1;
}

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

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

【考点】贪心算法｜二分查找

1. 🎯 考纲定位

考查 GESP 八级算法模块"贪心+二分优化 LIS"的经典解法。命题人卡住的是"只背结论、不理解本质"的考生，他们往往误以为 LIS 只有 O(n²) DP 解法，或混淆贪心与二分的时间复杂度。