Cod sursa(job #752380)

Utilizator davidoceaSintamarian David davidocea Data 28 mai 2012 15:26:55
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <cstdio>
#define l 100005
int f[l],dolari[l],pre[l],rez[l];
int main () {
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	int n,i,j,max=0,pozmax=0,sz=0,psol=0,sol=0;
	scanf("%d",&n);
	for(i=1;i<=n;++i){
		scanf("%d",&f[i]);
	}
	for(i=1;i<=n;++i){
		pozmax=0;
		max=0;
		for(j=i-1;j>=1;--j){
			if(f[j]<f[i]&&dolari[j]>max){
				pozmax=j;
				max=dolari[j];
			}
		}
		pre[i]=pozmax;
		dolari[i]=max+1;
	}
	
	for(i=1;i<=n;++i){
		if(dolari[i]>sol){
			sol=dolari[i];
			psol=i;
		}
	}
	for(;psol;psol=pre[psol]){
		rez[++sz]=f[psol];
	}
	printf("%d\n",sol);
	for(i=sz;i>0;--i){
		printf("%d ",rez[i]);
	}
	return 0;
}