Cod sursa(job #1456928)

Utilizator StefanRARapeanu-Andreescu Stefan StefanRA Data 2 iulie 2015 13:50:06
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <cstdio>
#include <cstdlib>
#include <cassert>
#define MAXN 100001
int n, v[MAXN], l[MAXN], next[MAXN], lmax, start;
int main()
{
	assert(freopen("scmax.in", "r", stdin));
	assert(freopen("scmax.out", "w", stdout));
	assert(scanf("%d", &n));
	for (int i=1;i<=n;++i)
		assert(scanf("%d", &v[i]));
	for (int i=n;i>=1;--i)
	{
		l[i]=1;
		for (int j=i+1;j<=n;++j)
			if (v[i]<v[j] && l[i]<1+l[j])
			{
				l[i]=l[j]+1;
				next[i]=j;
			}
		if (lmax<l[i])
		{
			lmax=l[i];
			start=i;
		}
	}
	printf("%d\n", lmax);
	for (int i=start;i!=0;i=next[i])
		printf("%d ", v[i]);
	return 0;
}