Cod sursa(job #196173)

Utilizator maria_pparcalabescu maria daniela maria_p Data 24 iunie 2008 19:45:41
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include<cstdio>
long a[100100],b[100100],t[100100],n,i,j,max,p,nr;
int main(){
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%ld",&n);
	for(i=0;i<n;i++)
		scanf("%ld",&a[i]);
	b[0]=1;t[0]=-1;
	for(i=1;i<n;i++){
		max=0;p=-1;
		for(j=0;j<i;j++)
			if(a[i]>a[j] && b[j]>max)max=b[j],p=j;
		b[i]=max+1;t[i]=p;
	}
	max=b[0];p=0;
	for(i=1;i<n;i++)
		if(b[i]>max)max=b[i],p=i;
	printf("%ld\n",max);
	nr=0;i=p;
	while(i!=-1){
		b[nr++]=a[i];
		i=t[i];
	}
	for(i=nr-1;i>=0;i--)
		printf("%ld ",b[i]);
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}