Cod sursa(job #246230)

Utilizator ovy2906Popescu Ovidiu ovy2906 Data 20 ianuarie 2009 13:17:02
Problema Subsir crescator maximal Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include<stdio.h>
int v[100000],n,x[100000],nr;
int find();
int lungime();
int main(){
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&v[i]);
	printf("%d",lungime());
	return 0;
}
int find(int val){
	int p=1,u=nr,mij;
	while(p<u){
		mij=(p+u)/2;
		if(val<=x[mij])
			u=mij;
		else
			p=mij+1;
	}
	if(x[p]<val)
		return p+1;
	return p;
}
int lungime(){
	nr=0;
	x[++nr]=v[1];
	for(int i=2;i<=n;++i)
		if(v[i]>x[nr])
			x[++nr]=v[i];
		else
			x[find(v[i])]=v[i];
	return nr;
}