题目描述

LIS

样例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve(){
    int n;
    cin >> n;
    vector<int> nums(n + 1,0);
    for(int i = 1; i <= n; i++){
        cin >> nums[i];
    }

    vector<int> tail; // tail数组(0 ~ n - 1 base)  tail[j] 表示长度为 j + 1 的上升子序列的末尾元素的最小值
    for(int i = 1; i <= n; i++){
        auto it = lower_bound(tail.begin(),tail.end(),nums[i]);
        if(it == tail.end()){
            tail.push_back(nums[i]);
        }else{
            *it = nums[i];
        }
    }

    cout << tail.size();

}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);

    solve();

    return 0;
}

算法1

(binary_Search) $O(n^2)$

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla