Cod sursa(job #308478)

Utilizator andrici_cezarAndrici Cezar andrici_cezar Data 27 aprilie 2009 12:55:52
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.47 kb
#include<fstream.h>
long n,a[100000],lg[100000],urm[100000],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];
for (i=n;i>=1;i--)
	{
	max=0;
	t=n;
	for (j=n;j>i;j--)
		if (a[i]<a[j] && lg[j]>max) {max=lg[j];t=j;}
	lg[i]=max+1;
	if (lg[i]>maxm) { maxm=lg[i];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;
}