Cod sursa(job #486399)

Utilizator selmaGoga Selma selma Data 21 septembrie 2010 16:42:48
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<fstream.h>
ifstream f("scmax.in");
ofstream g("scmax.out");
int i,h,pmax,max,j,a[100000],v[100000],l[100000],t[100000],n;
int main()
{
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	l[1]=1;
	for(i=2;i<=n;i++)
	{
		max=0;
		pmax=0;
		for(j=1;j<i;j++)
			if(v[i]>v[j] && l[j]>max)
				max=l[j],pmax=j;
		l[i]=max+1;
		t[i]=pmax;
	}
	max=0;
	for(i=1;i<=n;i++)
		if(l[i]>max)
		{
			max=l[i];
			pmax=i;
		}
	g<<max<<'\n';
	h=pmax;
	a[max+1]=v[h];
	for(i=max;i>=1;i--)
	{
		a[i]=v[t[h]];
		h=t[h];
	}
	for(i=2;i<=max+1;i++)
		g<<a[i]<<" ";
	return 0;
}