Cod sursa(job #676651)

Utilizator JBaccountCatalin JBaccount Data 9 februarie 2012 14:26:33
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <vector>
#include <string>

using namespace std;

#define NM 100005

int N, A[NM], B[NM], W[NM];

int main()
{
	freopen ("scmax.in", "r", stdin);
	freopen ("scmax.out", "w", stdout);
	
	scanf ("%d", &N);
	
	for (int i = 1; i <= N; ++i) scanf ("%d", &A[i]);
	
	for (int i = 1; i <= N; ++i) 
		for (int j = 0; j < i; ++j)
			if (A[i] > A[j] && B[j] + 1 > B[i])
			{
				B[i] = B[j] + 1;
				W[i] = j;
			}	
	
	int best = 0, p;		
	for (int i = 1; i <= N; ++i) 
		if (B[i] > best)		
		{
			best = B[i];
			p = i;
		}	
		
	printf ("%d\n", best);
	B[0] = 0;
	while (p)
	{
		B[++B[0]] = A[p];
		p = W[p];
	}	
		
	for (int i = B[0]; i > 0; --i) printf ("%d ", B[i]);
	
	return 0;
}