最长上升子序列

51Nod-2080-最长上升子序列

分析

/*
样例输入:
8
5 1 6 8 2 4 5 10
样例输出:
5
*/

f[i]记录长度为i的上升子序列的最小末尾元素值。

时间复杂度$O(nlogn)$。

实现

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
int n, a[N];
int f[N];

int main () {
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    int res = 1;
    f[1] = a[1];
    for (int i = 1; i <= n; ++ i) {
        if (f[res] < a[i]) {
            ++ res;
            f[res] = a[i];
        } else {
            int idx = lower_bound(f + 1, f + res + 1, a[i]) - f;
            f[idx] = a[i];
        }
    }
    cout << res << endl;
    return 0;
}