题目描述

blablabla

样例

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
const int N = 1005;

int a[N], f[N];
int cnt = -1;
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    // 二分查找
    auto find = [&](int left, int right, int x) {
        // 左闭右闭 二分
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (f[mid] >= x)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return right + 1 >= cnt + 1 ? -1 : right + 1;  // [0,size]
    };

    for (int i = 1; i <= n; i++) {
        int index = find(0, cnt, a[i]);
        if (index != -1)
            f[index] = a[i];
        else
            f[++cnt] = a[i];
    }
    cout << cnt + 1 << endl;
    return 0;
}