Cod sursa(job #445546)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 24 aprilie 2010 10:20:47
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <iostream>
#include <fstream>
#define max_N 100005

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int N, A[max_N], i , j, pre[max_N], maxim, best[max_N], pozinc;

int main()
{
	fin >> N;
	for(i = 1; i <= N; i ++)
		fin >> A[i];
	best[N] = 1;
	pre[N] = -1;
	for(i = N - 1; i >= 1; i --)
	{
		for(j = i + 1; j <= N; j ++)
			if(A[j] > A[i] && best[i] < best[j] + 1)
			{
				best[i] = best[j] + 1;
				pre[i] = j;
			}
		if(best[i] > maxim)
			maxim = best[i], pozinc = i;
	}
	
	fout << maxim << "\n";
	i = pozinc;
	while(i != -1)
	{
		fout << A[i] << " ";
		i = pre[i];
	}
	return 0;
}