Cod sursa(job #523246)

Utilizator andrici_cezarAndrici Cezar andrici_cezar Data 17 ianuarie 2011 15:41:57
Problema Subsir crescator maximal Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<stdio.h>

long n, maxlg, indicemaxlg, max, lg[1001], u[1001], a[1001], nrr;

int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	
		scanf("%ld", &n);
		
		for (long i = 1; i <= n; i ++)
			scanf("%ld", &a[i]);
		max = 0;
		for (long j = n; j >= 1; j --)
		{
			maxlg = 0;
			indicemaxlg = 0;
			for (long i = j + 1; i <= n;  i ++)
				if (maxlg < lg[i] && a[i] > a[j])
				{
					maxlg = lg[i];
					indicemaxlg = i;
				}
			lg[j] = maxlg+1;
			u[j] = indicemaxlg;
			if (lg[j] > max) max = lg[j], nrr = j;
		}
		
		printf("%ld\n", max);
		
		while (nrr != 0)
		{
			printf("%ld ", a[nrr]);
			nrr = u[nrr];
		}
	
	return 0;
}