Cod sursa(job #547888)

Utilizator alexdmotocMotoc Alexandru alexdmotoc Data 6 martie 2011 19:46:16
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>
using namespace std;

long long n , x[100005] , best[100005] , cont , sir[100005];


int main ()
{
	ifstream f ("scmax.in");
	ofstream g ("scmax.out");
	
	int max = 0;
	
	f >> n;
	
	for (long long i = 1 ; i <= n ; ++i)
		f >> x[i];
	
	best[1] = 1;
	
	for (long long i = 2 ; i <= n ; ++i)
	{
		cont = 0;
		
		for (long long j = 1 ; j < i ; ++j)
			if (x[j] < x[i] && best[j] < best[j + 1] + 1)
			{
				cont++;
				sir[cont] = x[j];
			}
		
		cont++;
		best[i] = cont;	
		sir[cont] = x[i];
		
		if (best[i] > max)
			max = best[i];
	}
	
	g << max << "\n";
	
	for (long long i = 1 ; i <= max ; ++i)
		g << sir[i] << " ";
	
	g << "\n";
	
	return 0;
}