Cod sursa(job #422987)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 23 martie 2010 13:22:44
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<stdio.h>
FILE*f=fopen("scmax.in","r");
FILE*g=fopen("scmax.out","w");
int a[100005],k,sol[100005],v[100005],poz,i,n,j,t[100005],u,max,x;
int main () {
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(f,"%d",&a[i]);
	for(i=1;i<=n;i++){
		max=0;poz = 0;
		for(j=1;j<=i-1;j++){
			if(a[i]>a[j]&&v[j]>max){
				max=v[j];
				poz=j;
			}
		}
		v[i]=max+1;
		t[i]=poz;
		
		if(v[i]>v[x]){
			x=i;
		}
	}
	u=x;
	while(u!=0){
		sol[++k]=a[u];
		u=t[u];
	}
	fprintf(g,"%d\n",v[x]);
	for(i=k;i>=1;i--)
		fprintf(g,"%d ",sol[i]);
	
	fclose(f);
	fclose(g);
	return 0;
}