最长上升子序列

朴素版n^2^

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;
int a[N], f[N];
int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++){
        f[i] = 1;
        for(int j = 1; j < i; j ++)
            if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++) ans = max(ans, f[i]);
    cout << ans;
    return 0;
}

优化版nlogn

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int a[N];
int main(){
    int n;
    cin >> n;
    vector<int> arr;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    arr.push_back(a[1]);
    for(int i = 2; i <= n; i ++){
        if(a[i] > arr.back()) arr.push_back(a[i]);
        else *lower_bound(arr.begin(), arr.end(), a[i]) = a[i];
    }
    cout << arr.size();
    return 0;
}