Cod sursa(job #317790)

Utilizator MikeysMihai Tiganus Mikeys Data 25 mai 2009 09:00:59
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream.h>

int c[100000],a[100000];

int main()
{
	ifstream in("scmax.in");
	ofstream out("scmax.out");
	long v[100000],n,max,i,j,maxabs,maxabsi;
	in >>n;
	for(i=0;i<n;i++)
		in>>v[i],a[i]=-1;
	c[0]=1;
	for(i=1;i<n;i++)
	{
		max=1;
		for(j=0;j<n;j++)
		{
			if(v[i]>v[j])
				if(max<c[j]+1)
				{
					max=c[j]+1;
					a[i]=j;
					if(maxabs<max)
						maxabs=max,maxabsi=i;
				}
		}
		c[i]=max;
	}
	
	out <<maxabs;
	i=maxabsi;
	n=maxabs;
	while(i!=-1)
	{
		c[maxabs--]=v[i];
		i=a[i];
	}
	out <<"\n";
	for(i=1;i<=n;i++)
		out <<c[i]<<" ";
	in.close();
	out.close();
	return 0;
}