Cod sursa(job #521125)

Utilizator ivan_marianIvan Liviu Marian ivan_marian Data 11 ianuarie 2011 13:24:09
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <stdio.h>
FILE *f=fopen("scmax.in","r");
FILE *g=fopen("scmax.out","w");
int max,p,mx,n,a[100001],b[100001],i,j;
void rec(int p){
	int i;
	if(p>0)
	{
		for(i=p-1;i>=1;i--)
			if(a[i]<a[p]&&b[i]==b[p]-1)
			{	rec(i);
			 break;}
				
	fprintf(g,"%d ",a[p]);	
}
}
int main() {
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(f,"%d",&a[i]);
	mx=0;b[1]=1;
	for(i=2;i<=n;i++) {
		max=1;
		for(j=i-1;j>=1;j--)
			if(a[i]>a[j]&&max<b[j]+1)
				max=b[j]+1;
		b[i]=max;
		if(mx<max) {
			mx=max;
			p=i;
		}
	}
	fprintf(g,"%d\n",mx);
	rec(p);
	return 0;
}