Cod sursa(job #741956)

Utilizator alexdmotocMotoc Alexandru alexdmotoc Data 27 aprilie 2012 16:46:40
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>
#include <iostream>

using namespace std;

#define maxN 100005

int best[maxN] , sol[maxN] , x[maxN] , tata[maxN];
int best_max , poz , poz_max , dim , N , sol_max;

int main ()
{
	freopen ("scmax.in" , "r" , stdin);
	freopen ("scmax.out" , "w" , stdout);
	
	scanf ("%d" , &N);
	
	for (int i = 1 ; i <= N ; ++i)
	{
		scanf ("%d" , &x[i]);
		
		best_max = 0;
		
		for (int j = 1 ; j < i ; ++j)
			if (best[j] > best_max && x[j] < x[i])
			{
				best_max = best[j];
				tata[i] = j;
			}
		
		
		best[i] = best_max + 1;
		
		if (best[i] > sol_max)
		{
			sol_max = best[i];
			poz_max = i;
		}
	}
	
	printf ("%d\n" , sol_max);
	
	for (int i = poz_max ; i >= 1 ; i = tata[i])
		sol[++dim] = x[i];
	
	for (int i = dim ; i >= 1 ; --i)
		printf ("%d " , sol[i]);
	
	return 0;
}