Cod sursa(job #460275)

Utilizator ms-ninjacristescu liviu ms-ninja Data 1 iunie 2010 19:52:54
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>

using namespace std;
#define dim 100001

int v[dim], best[dim], c[dim];

int main()
{
	long nr, i, j, n, max;
	ifstream fin("scmax.in");
	ofstream fout("scmax.out");
	
	fin>>n;
	nr=0;
	
	for(i=1;i<=n;++i)
	{
		fin>>v[i];
		
		max=0;
		
		for(j=i-1;j>=1;--j)
			if(v[i]>v[j])
				if(best[j]>max)
					max=best[j];
		
				
				best[i]=max+1;
				if(best[i]>nr)
					nr=best[i];
	}
	fout<<nr <<'\n';
	long f=0;
	for(i=n;i>=1;--i)
	{
		if(best[i]==nr)
		{
			--nr;
			++f;
			c[f]=v[i];
		}
	}
	
	for(i=f;i>=1;--i)
		fout<<c[i] <<" ";
	return 0;
}