Cod sursa(job #579712)

Utilizator GaborGabrielFMI - GabrielG GaborGabriel Data 12 aprilie 2011 13:35:45
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream.h>
ifstream f("scmax.in");
ofstream g("scmax.out");
long long n,numar,inainte[100001],subsir[100001],sir[100001],i,ss[100001],vf=0;

int cauta(long long k)
{
	int min=0,j=0;
	for(j=n;j>i;j--)
		if(sir[j]<k && sir[min]<sir[j])
			min=j;
	return min;
}

int main()
{
	long long aux;
	f>>n;
	for(i=n;i>=1;i--)
	{
		f>>sir[i];
		aux=cauta(sir[i]);
		subsir[i]=subsir[aux]+1;
		inainte[i]=aux;
	}
	int max=0,ii;
	for(i=1;i<=n;i++)
		if(subsir[max]<subsir[i])
			max=i;	
	while(max)
	{
		ss[++vf]=sir[max];
		max=inainte[max];
	}
	g<<vf<<'\n';
	for(i=vf;i>=1;i--)
		g<<ss[i]<<' ';
	g<<'\n';
	f.close();
	g.close();
	return 0;
}