Cod sursa(job #412285)

Utilizator n3msizN3msiz n3msiz Data 5 martie 2010 14:24:54
Problema Subsir crescator maximal Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<stdio.h>

int n,v[100003],pozi,max,maxsir,L[100003],i,j,pmax,t[100003];

int main(){
	FILE*f=fopen("scmax.in","r");
	FILE*g=fopen("scmax.out","w");
	
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(f,"%d",&v[i]);
	
	L[1]=1;
	for(i=2;i<=n;i++){
		max=0;
		for(j=i-1;j>=1;j--){
			if(max<L[j] && v[i]>v[j]){
				max=L[j];
				pmax=j;
			}
		}
		L[i]=max+1;
		t[i]=pmax;
		
		if(L[i]>maxsir){
			maxsir=L[i];
			pozi=i;
		}
	}
	
	fprintf(g,"%d\n",maxsir);
	
	while(pozi){
		fprintf(g,"%d ",v[pozi]);
		pozi=t[pozi];
	}
	
	//fprintf(g,"%d %d",pozi,maxsir);
	
	fclose(f);
	fclose(g);
	return 0;
}