Cod sursa(job #524458)

Utilizator aelenei_vladAelenei Vlad aelenei_vlad Data 21 ianuarie 2011 16:59:39
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include<fstream.h>
long n,a[100000],Lg[100000],Urm[100000],im,max;
int main ()
{long i,j;
ifstream f("scmax.in");
ofstream g("scmax.out");
f>>n;
for(i=0;i<n;i++)
	f>>a[i];
Lg[n]=1;
Urm[n]=0;
for(i=n;i>=1;i--)
{max=0;
im=0;
for(j=i-1;j<=n;j++)
	if(a[i]<a[j]&&max<Lg[j])
	{max=Lg[j];
	im=j;}
	Lg[i]=max+1;
	Urm[i]=im;}
max=Lg[i];im=1;
for(i=2;i<=n;i++)
	if(max<Lg[i])
	{max=Lg[i];
	im=i;
	}
	g<<max<<'\n';
	do
	{g<<a[im]<<" ";
	im=Urm[im];
	}
	while(im!=0);
	g<<'\n';
	f.close();
	g.close();
	return 0;
}