POJ 3903 Stock Exchange 最长上升子序列入门题

佚名 6年前 (2019-05-04) 随笔 1200人围观抢沙发百度已收录

题目链接：http://poj.org/problem?id=3903
最长上升子序列入门题。
算法时间复杂度 O(n*logn) 。
代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int n, a[maxn], f[maxn], maxlen = 0;

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