Cod sursa(job #579790)

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

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

int main()
{
	long long aux;
	f>>n;
	for(i=1;i<=n;i++)
		f>>sir[i];
	subsir[n]=1;	
	sir[n+1]=2000000000;
	for(i=n-1;i>=1;i--)
	{		
		aux=cauta(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;	
	g<<subsir[max]<<'\n';
	while(max)
	{
		g<<sir[max]<<' ';
		max=inainte[max];
	}
	g<<'\n';
	f.close();
	g.close();
	return 0;
}