Cod sursa(job #658392)

Utilizator Marius_mFMI-M2 Marius Melemciuc Marius_m Data 8 ianuarie 2012 19:14:12
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<stdio.h>
#define Nmax 100005

using namespace std;

FILE *c,*d;
int n,v[Nmax],best[Nmax],inext[Nmax],max,p;

void read()
{
	int i;
	fscanf(c,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(c,"%d",&v[i]);
}

void solve()
{
	int i,j;
	best[n]=1;
	inext[n]=-1;
	max=1;
	p=n;
	for(i=n-1;i>=1;i--)
	{
		best[i]=1;
		inext[i]=-1;
		for(j=i+1;j<=n;j++)
			if(v[j]>v[i]&&(best[j]+1>best[i]))
			{
				best[i]=best[j]+1;
				inext[i]=j;
				if(best[i]>max)
				{
					max=best[i];
					p=i;
				}
			}
	}
}

void subsir()
{
	int i;
	fprintf(d,"%d\n",max);
	i=p;
	while(i!=-1)
	{
		fprintf(d,"%d ",v[i]);
		i=inext[i];
	}
}

int main()
{
	c=fopen("scmax.in","r");
	d=fopen("scmax.out","w");
	read();
	solve();
	subsir();
	fclose(c);
	fclose(d);
	return 0;
}