Cod sursa(job #445549)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 24 aprilie 2010 10:26:52
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <cstdio>
#define max_N 100005

using namespace std;

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

int main()
{
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);
	scanf("%d", &N);
	for(i = 1; i <= N; i ++)
		scanf("%d", &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;
		}
	}
	
	printf("%d\n", maxim);
	i = pozinc;
	while(i != -1)
	{
		printf("%d ", A[i]);
		i = pre[i];
	}
	return 0;
}