C++14(g++5.4) 解法, 执行用时: 28ms, 内存消耗: 476K, 提交时间: 2019-03-16 15:48:52

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[1000001]={0};
int main()
{
	int n,y,c=0,d,*x;
	scanf("%d",&n);
	for(y=0;y<n;y++)
	{
		scanf("%d",&d);
		x=lower_bound(a,a+c,d);
		*x=d;
		if(x==a+c)
			c++;
	}
	printf("%d",c);
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 54ms, 内存消耗: 436K, 提交时间: 2023-03-14 11:00:08

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
    set<int>s;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        auto k=s.lower_bound(x);
        if(k!=s.end())s.erase(k);
        s.insert(x);
    }
    cout<<s.size()<<endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 34ms, 内存消耗: 504K, 提交时间: 2020-09-26 23:22:19

#include<bits/stdc++.h>
using namespace std;
set<int>s;
int main()
{
	int n,t;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d",&t);
		if(s.upper_bound(t)!=s.end())
		s.erase(s.upper_bound(t));
		s.insert(t);
	}
	printf("%d",s.size());
}