题意
鹏神意外得到了神灯。
神灯中冒出了灯神，灯神说道：“我将给你一个有序的数列，你可以在保证原有顺序不变的前提下，挑出任意多的数。如果你挑出的数字是严格升序的，那么这段数字的个数就是你女朋友的个数。”
“妈的智障。”鹏神骂道。
但是鹏神还是希望自己能有尽可能多的女朋友。所以他求救于你，希望你能帮他算出他最多能有多少女朋友。
解题
LIS模板题。
最长上升子序列的解法比较多。
这里用时间复杂度为O（nlogn)的解法。
AC代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;const int maxn=1e3+7;
int dp[maxn],a[maxn];int main()
{int N;while(cin>>N){for(int i=1;i<=N;i++)cin>>a[i];memset(dp,0x3f,sizeof(dp));for(int i=1;i<=N;i++){int pos=lower_bound(dp,dp+N,a[i])-dp;//cout<<dp[pos]<<endl;//cout<<pos<<endl;dp[pos]=a[i];}int ans=0;for(int i=0;i<N;i++)if(dp[i]!=INF) ans++;cout<<ans<<endl;}return 0;
}