Cod sursa(job #521128)

Utilizator NadoluBogdanNadolu Bogdan NadoluBogdan Data 11 ianuarie 2011 13:34:11
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<stdio.h>
FILE *f=fopen("scmax.in","r");
FILE *g=fopen("scmax.out","w");
int i,j,n,a[100001],b[100001],mx,max,p;

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;
}