Cod sursa(job #1082758)

Utilizator robert_stefanRobert Stefan robert_stefan Data 14 ianuarie 2014 21:44:22
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
//O(n^2)
#include <fstream>
#define IN "scmax.in"
#define OUT "scmax.out"
#define NMAX 100005

using namespace std;

ifstream in(IN);
ofstream out(OUT);

int v[NMAX], l[NMAX], n;

int main()
{
	int i, j, vmax=1, indmax=n;
	in>>n;
	for(i=1; i<=n; ++i)
		in>>v[i];
	l[n]=1;
	for(j=n-1; j>=1; --j)
		for(i=j+1; i<=n; ++i)
		{
			if(v[j]<v[i] && l[j]<l[i])
				l[j]=l[i]+1;
			if(!l[j])
				l[j]=1;
			if(vmax<l[j])
				vmax=l[j],
				indmax=j;
		}
	out<<vmax<<'\n';
	out<<v[indmax]<<' ';
	--vmax;
	while(vmax)
	{
		while(l[indmax]!=vmax)
			++indmax;
		out<<v[indmax]<<' ';
		--vmax;
	}
	in.close();
	out.close();
	return 0;
}