Cod sursa(job #694368)

Utilizator TheOnlyExceptionBarna Monica TheOnlyException Data 27 februarie 2012 20:26:11
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int n,i,j,nr,x;
int v[100003],loc[100003];

void citire()
{
	f >> n;
	for(i=1;i<=n;i++)
		f >> v[i];
}

int cauta()
{
	int m=0;
	for(j=x+1;j<=n;j++)
		if(loc[j]>m)
			if(v[x]<v[j])
				m=loc[j];
	return m+1;
}
		
void locul()
{
	loc[n]=1;
	for(i=n-1;i>=1;i--)
	{
		x=i;
		loc[i]=cauta();
		if(loc[i]>nr) nr=loc[i];
	}
	g << nr << "\n";
}

void subsir()
{
	for(i=1;i<=n;i++)
	{
		if(loc[i]==nr)
		{
			g << v[i] << " ";
			nr=nr-1;
		}
		if(nr==0) break;
	}
}

int main()
{
	citire();
	locul();
	subsir();
	return 0;
}