题解 | #最长不下降子序列#

传统的dp方法的时间复杂度是O(n²)

可以用O(n logn)时间复杂度求得最长长度,但仅是序列长度不是序列本身

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


signed main(){
    HelloWorld;
    
    int n; cin >> n;
    vector<int> a(n + 1), len;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++){
        if(!len.size() || a[i] >= len.back()) len.push_back(a[i]);
        else *upper_bound(len.begin(), len.end(), a[i]) = a[i];
    }
    cout << len.size() << endl;
    return 0;
}

为什么可以直接替换成a[i]？

原因是对于长度为 k 的不下降子序列，我需要记录 “能找到的最小末尾元素”，至于这个元素在原序列中是第几个出现的，不重要 —— 只要它能构成一个合法的、长度为 k 的不下降子序列即可