记录编号	543744	评测结果	AAAAAAAAAA
题目名称	最长上升子序列	最终得分	100
用户昵称	ShallowDream雨梨	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2019-10-09 20:01:36	内存使用	13.68 MiB

    #include<bits/stdc++.h>
    #define int long long 
    using namespace std; 
    const int maxn=1005;
    int dp[maxn],a[maxn];
    signed main(){	
    	
    		freopen("lis1.in","r",stdin);
    	freopen("lis1.out","w",stdout);
    	int n,pos=1;
    	cin>>n;
    	for(int i=1;i<=n;i++)cin>>a[i];
    	dp[1]=a[1];
    	for(int i=2;i<=n;i++){
    	if(a[i]>dp[pos])dp[++pos]=a[i];
    	else
    	dp[lower_bound(dp+1,dp+1+pos,a[i])-dp]
    	=a[i];
    	}
    	cout<<pos;
        return 0;}