Cod sursa(job #406303)

Utilizator xtephanFodor Stefan xtephan Data 1 martie 2010 13:29:07
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<stdio.h>
#include<algorithm>

using namespace std;


long a[100003];
long c[100003];
long pre[100003];
long n;


void cit();
void rez();
void afis();


int main() {
	
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);
	
	cit();
	rez();
	afis();
	
	return 0;
}


void cit() {
	
	scanf("%ld", &n);
	
	for(long i=1; i<=n; i++)
		scanf("%ld", &a[i]);
}


void rez() {
	
	c[n]=1;
	pre[n]=-1;
	
	for(long i=n-1; i>=1; --i) {
		
		c[i]=1;
		pre[i]=-1;
		int p=-1;
		int kk=-1;
		
		kk=c[i];
		
		for(long j=i+1; j<=n; j++) {
			
			/*
			if(a[i]<a[j] && c[i]<c[j]+1) {
				//c[i]=max(c[i], c[j]+1);
				c[i]=c[j]+1;
				pre[i]=j;
			}
			*/
			
			if(a[i]<a[j] && kk<c[j]+1)
				kk=c[j]+1, p=j;
		}
		
		if(p!=-1)
			c[i]=c[p]+1, pre[i]=p;
		
	}
	
}


void afis() {
	
	long tot=1;
	long inc=n;
	
	
	for(long i=1; i<=n; i++)
		//tot=max(tot,c[i]);
		if(tot<c[i])
			tot=c[i], inc=i;
	
	printf("%ld\n", tot);

	while(pre[inc]!=-1) {
		printf("%ld ", a[inc]);
		inc=pre[inc];
	}

	
	printf("%ld ", a[inc]);
}