Cod sursa(job #194799)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 14 iunie 2008 11:22:36
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
# include <cstdio>
const int N=1000005;
int n,v[N],lung[N],pred[N];
void read(){
	int i;
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;++i)
		scanf("%d",&v[i]);
}
int max(int x){
	int i,max=0,j=0;
	for (i=1;i<x;++i)
		if (lung[i]>max&&v[i]<v[x]){
			j=i;
			max=lung[i];
		}
	return j;
}
void write(int x){
	if (pred[x])
		write(pred[x]);
	printf("%d ",v[x]);
}
void rezolva(){
	int i,j;
	lung[0]=0;
	v[n+1]=2000000001;
	for (i=1;i<=n;++i){
		j=max(i);
		lung[i]=lung[j]+1;
		pred[i]=j;
	}
	j=max(n+1);
	printf("%d\n",j);
	write(j);
	printf("\n");
}
int main(){
	read();
	rezolva();
}