Cod sursa(job #752375)

Utilizator ephgstefana gal ephg Data 28 mai 2012 15:20:49
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
#define BM 100005
int copii[BM],pre[BM],rez[BM],dolar[BM],n,dim;
int main () {
	int i,j,maxim=0,poz=1;
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;++i)scanf("%d",&copii[i]);
	for(i=1;i<=n;++i){
		poz=0;
		maxim=0;
		for(j=1;j<i;++j)if(copii[i]>copii[j]&&maxim<dolar[j]){
			maxim=dolar[j];
			poz=j;
			
		}
		dolar[i]=maxim+1;
		pre[i]=poz;
	}
	maxim=0;
	for(i=1;i<=n;++i)if(maxim<dolar[i]){
		maxim=dolar[i];
		poz=i;
	}
	//for(i=1;i<=n;++i)fprintf(stderr,"%d ",pre[i]);
	for(;poz!=0;){
		//fprintf(stderr,"aici");
		rez[++dim]=copii[poz];
		poz=pre[poz];
	}
	printf("%d\n",dim);
	for(i=dim;i;--i)printf("%d ",rez[i]);
	return 0;
}