Cod sursa(job #640839)

Utilizator alexdmotocMotoc Alexandru alexdmotoc Data 26 noiembrie 2011 16:19:04
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <cstdio>

using namespace std;

#define maxN 100005

long long x[maxN];
int N , maxx , maxim = 0 , best[maxN] , pre[maxN] , fin[maxN] , dim = 0 , pozmax;

int main ()
{
	freopen ("scmax.in" , "r" , stdin);
	freopen ("scmax.out" , "w" , stdout);
	
	scanf ("%d" , &N);
	
	for (int i = 1 ; i <= N ; ++i)
	{
		scanf ("%lld" , &x[i]);
		
		maxx = 0;
			
		for (int j = i - 1 ; j >= 1 ; --j)
			if (x[j] < x[i] && best[j] > maxx)
			{
				maxx = best[j];
				pre[i] = j;
			}
			
		best[i] = maxx + 1;
		
		if (best[i] > maxim)
		{
			maxim = best[i];
			pozmax = i;
		}
	}
	
	printf ("%d\n" , maxim);
	
	for (int i = pozmax ; i ; i = pre[i])
		fin[++dim] = x[i];
	
	for (int i = dim ; i >= 1 ; --i)
		printf ("%d " , fin[i]);

	return 0;
}