Cod sursa(job #699085)

Utilizator mihai_bogdaannMihai Bogdan mihai_bogdaann Data 29 februarie 2012 17:26:52
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include<fstream>
ifstream fin("scmax.in");
ofstream fout("scmax.out");
long int n,a[100001],max,im,lg[100001],u[100001],i,j,nr1;
int main()
{
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>a[i];
	lg[n] = 1;
	u[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;
		u[i] = im;
	}
	max=0;
	for(i=1;i<=n;i++)
		if(max<lg[i])
			max=lg[i],im=i;
	fout<<max<<'\n';
	while(a[im])
	{
		fout<<a[im]<<' ';
		im=u[im];
	}
}