Cod sursa(job #522193)

Utilizator tangredonSilviu Georgescu tangredon Data 14 ianuarie 2011 15:15:18
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#define DIM 100000
using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int i,j,n;
int v[DIM];
int L[DIM];
int T[DIM];
int Max,p;
int X;
int S[DIM];
int k;

int main ()
{
	for ( f >> n, i = 1; i <= n ; i++ )
		f >> v[i];
	
	L[1] = 1;
	
	for ( i = 2; i <= n; i++ )
	{
		Max = 0; 
		p = 0;
		for ( j = 1; j < i; j++ )
			if ( v[j] < v[i] && L[j] > Max )
			{
				Max = L[j];
				p = j;
			}
		L[i] = 1 + Max;
		T[i] = p;
	}
	
	for (Max = 0, i = 1; i <= n; i++ )
	{
		if ( L[i] > Max )
		{
			Max = L[i];
			X = i;
		}
	}
	
	k=0;
	g << Max << '\n';
	i = X;
	while ( i )
	{
		S[++k] = v[i];
		i = T[i];
	}
	
	for ( ; k > 0 ; k--  )
		g << S[k] << ' ';
}