Cod sursa(job #809145)

Utilizator adeath_metalSiriteanu Andrei adeath_metal Data 7 noiembrie 2012 22:14:58
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n,l[100001],lmax[100001],urm[100001],max,pozitie;
int main()
{
	max=lmax[1];
	pozitie=1;
	
	fin>>n;
	for(int i=1;i<=n;i++)
	fin>>l[i];

	lmax[n]=1;
	urm[n]=-1;
	for(i=n-1;i>=1;i--)
	{
		lmax[i]=1; urm[i]=-1;
		for(j=i+1;j<=n;j++)
		if(l[i]<l[j] && lmax[i]<1+lmax[j])
		{
			lmax[i]=1+lmax[j];
			urm[i]=j;
		}
	}
	
	
	for(i=1;i<=n;i++)
	if(max<lmax[i])
	{
		max=lmax[i];
		pozitie=i;
	}
	fout<<max<<'\n';
	i=pozitie;
	while(i!=-1)
	{
		fout<<l[i]<<' ';
		i=urm[i];
	}

	return 0;
}