单选题 适中
#20174

下面 LIS 函数试图求出最长上升子序列的长度,其时间复杂度为?( ) # define INT_MIN ( - 1000 ) int LIS ( vector…

下面 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;
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:C
这道题暂未补解析。