Cod sursa(job #844726)

Utilizator arrayAnghel Mihai array Data 29 decembrie 2012 19:00:15
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
using namespace std;
const char iname[] = "scmax.in";
const char oname[] = "scmax.out";
ifstream fin(iname);
ofstream fout(oname);
int N , i , j , maxv , lgmax , st_p;
int v[ 100004 ];
int best[ 100004 ] , pre[ 100004 ];
int main()
{
	fin >> N;
	for (i = 1; i <= N; ++i)
		fin >> v[i];
	best[N] = 1;
	pre[N] = -1;
	for (i = N - 1; i >= 1; --i)
	{
		pre[i] = -1;
		best[i] = 1;
		for (j = i + 1; j <= N; ++j)
		{
			if (best[i] < best[j] + 1 && v[i] < v[j])
			{
				pre[i] = j;
				best[i] = best[j] + 1;
				if (best[i] > lgmax)
					lgmax = best[i] , st_p = i;
			}
		}
	}
	fout << lgmax << '\n';
	i = st_p;
	while (i != -1)
	{
		fout << v[i] << ' ';
		i = pre[i];
	}
	return 0;
}