Cod sursa(job #486491)

Utilizator delia_popescupopescu delia delia_popescu Data 21 septembrie 2010 19:52:06
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<stdio.h>
int n,i,j,max,L[100000],pmax,T[100000],poz[100000];
int v[100000];
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;
		pmax=0;
		for(j=1;j<i;j++)
			if(v[i]>v[j] && L[j]>max){
				max=L[j];
				pmax=j;
			}
		L[i]=max+1;
		T[i]=pmax;
	}
	max=0;
	for(j=1;j<=i;j++)
		if(L[j]>max){
			max=L[j];
			pmax=j;
		}
		fprintf(g,"%d\n",max);
	poz[max+1]=v[pmax];	
	for(i=max;i>=1;i--){
		poz[i]=v[T[pmax]];
		pmax=T[pmax];
	}
	
	for(i=2;i<=max+1;i++)
		fprintf(g,"%d ",poz[i]);
	
	


	

	fclose(f);
	fclose(g);
return 0;
}