Cod sursa(job #718700)

Utilizator Theorytheo .c Theory Data 20 martie 2012 23:38:48
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 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 - 1; i > 0; i-- )
	{
		a[i] = 1;
		for( j = i + 1 ; j <= n ; 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;
}