Cod sursa(job #752385)

Utilizator andreidanAndrei Dan andreidan Data 28 mai 2012 15:32:30
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <cstdio>
int dolar[100006],pre[100006],rez[103476],v[100005];
int main (){
	int i,j,n,max=0,maxpoz=0,psol=0,sz=0,sol=0;
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d", &n);
	
	for(i=1;i<=n;++i)
		scanf("%d", &v[i]);
	
	for(i=1;i<=n;++i){
		max=0;
		maxpoz=0;
		for(j=i-1;j>=1;--j)
			if(v[j]<v[i]&&dolar[j]>max){
				maxpoz=j;
				max=dolar[j];
			}
			dolar[i]=max+1;
			pre[i]=maxpoz;

	}
	for(i=1;i<=n;++i)
		if(dolar[i]>sol){
		sol=dolar[i];
		psol=i;
		}
		printf("%d\n", sol);
	for(;psol;psol=pre[psol]) rez[++sz]=v[psol];
	for(i=sz;i;--i) printf("%d ", rez[i]);
}