Cod sursa(job #522414)

Utilizator alexstefyhrStefanescu Alexandru Marian alexstefyhr Data 15 ianuarie 2011 09:26:45
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.52 kb
#include<fstream.h>
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n,i,j,max,im,a[1000],lg[100],urm[100];
int main()
{
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>a[i];
	lg[n]=1;
	urm[n]=0;
	for(i=n-1;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[1];
	im=1;
	for(i=2;i<=n;i++)
		if(max<lg[i])
			max=lg[i],im=i;
	fout<<max<<'\n';
	do
	{
		fout<<a[im]<<' ';
		im=urm[im];
	}while(im!=0);
	return 0;
}