Cod sursa(job #687684)

Utilizator mihai_bogdaannMihai Bogdan mihai_bogdaann Data 22 februarie 2012 18:02:50
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<stdio.h>

FILE *fin = fopen("scmax.in","r");
FILE *fout = fopen("scmax.out","w");

int indi,a[100001],nr[100001],urm[100001],ultim[100001],n,i,j,max;
int main()
{
	fscanf(fin,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(fin,"%d",&a[i]);
	nr[n] = 1;
	urm[n] = 0;
	ultim[n] = a[n];
	for(i=n-1;i>=1;i--)
	{
		for(j=i+1;j<=n;j++)
		{
			if(a[i]<a[j] && nr[j]+1>max)
			{
				nr[i] = nr[j]+1;
				urm[i] = j;
				if(nr[i]>max)
					max = nr[i],indi = i;
			}
		}
	}
	fprintf(fout,"%d\n",max);
	while(urm[indi])
	{
		fprintf(fout,"%d ",a[indi]);
		indi = urm[indi];
	}
	
	fprintf(fout,"%d ",a[indi]);
}