(贪心 + 二分)

时间复杂度 $O(nlog{n})$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int n;
int a[N];
int f[N];

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++ )
        scanf("%d", &a[i]);

    int len = 0;        //len是f数组中数的个数
    for(int i = 0; i < n; i ++ )
    {
        int l = 0, r = len;         //二分找到第一个大于等于a[i]的位置
        while(l < r){
            int mid = l + r >> 1;
            if(f[mid] >= a[i])  r = mid;
            else    l = mid + 1;
        }
        if(l == len)    f[len ++ ] = a[i];      //如果f中不存在大于等于a[i]的数，就把a[i]加到f数组中
        else    f[l] = a[i];        //如果存在，则把当前找到的位置上的数换成a[i]
    }

    printf("%d\n", len);

    return 0;
}