Cod sursa(job #308479)

Utilizator andrici_cezarAndrici Cezar andrici_cezar Data 27 aprilie 2009 13:03:21
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.5 kb
#include<fstream.h>
long n,a[100001],lg[100001],urm[100001],max,tt,maxm,t,j,i;

int main()
{
ifstream f("scmax.in");
ofstream g("scmax.out");
f>>n;
for (i=1;i<=n;i++)
	f>>a[i];
lg[n]=1;
urm[n]=0;
for (i=n-1;i>=1;i--)
	{
	max=0;
	t=0;
	for (j=n;j>i;j--)
		if (a[i]<a[j] && lg[j]>max) {max=lg[j];t=j;}

	lg[i]=max+1;

	if (max>maxm) { maxm=max+1;tt=i;}
	//if (t==i) t=0;
	urm[i]=t;
	}
g<<maxm<<'\n';
for (i=1;i<=maxm;i++)
	{
	g<<a[tt]<<' ';
	tt=urm[tt];
	}
g.close();
return 0;
}