Cod sursa(job #718684)

Utilizator Theorytheo .c Theory Data 20 martie 2012 23:21:17
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<fstream>
#define nmax 100003
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int v[nmax], i, j, a[nmax],n,m,last[nmax],lmax;
void read()
{
	fin >> n ; 
	for( i = 1; i <= n; i++ )
		fin >> v[i];
	a[ n ] = 1;
	for( i = n; i > 0; i-- )
	{
		for( j = n ; j > i  ; j-- )
		{
			if(v[i] < v[j] && a[i] < a[j] + 1 )
			{
				
				a[i] = a[j] + 1;
				last[i] = j; 
			}
			
		}
		
	}
	for( i = 1; i <= n; i++)
		if(a[i] > lmax)
		{
			j = i;
			lmax = a[i]; 
		}
		
	fout << lmax << '\n' ;
	for ( i = 1; i <= lmax; i++ )
	{
			fout << v[ j ] << " " ;

		j = last[j] ;
	}
		
}
int main()
{
	read();
	fin.close();
	fout.close();
	return 0;
}