ダイナミック企画(最長上昇サブシーケンス)
5227 ワード
良い説明:http://www.cnblogs.com/GodA/p/5180560.html
良いコード:
良いコード:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=1e5+100;
const int MOD=1e9+7;
#define INF 0x3f3f3f3f
typedef long long LL;
typedef unsigned long long llu;
int dp[maxn];
int main(){
int n;
int i;
int a;
for(i=0;i<maxn;i++)
dp[i]=INF;
int len=0;
dp[0]=-INF;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a);
int lo=0;
int ub=len+1;
while(ub-lo>1){
int mid=(lo+ub)>>1;
if(dp[mid]<a)
lo=mid;
else ub=mid;
}
dp[lo+1]=a;
len=max(len,lo+1);
}
cout<<len<<endl;
return 0;
}