Cod sursa(job #395964)

Utilizator alutzuAlexandru Stoica alutzu Data 14 februarie 2010 10:20:41
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<cstdio>

int x [ 1 << 17 ] ;
int lung [ 1 << 17 ] ; 
int pred [ 1 << 17 ] ; 

void afis ( int var )
{
	if ( var == 0 ) return ;
	afis ( pred[var] ) ;
	printf ( "%d " , x [ var ] ) ;
}

int main ( )
{
	
	freopen ( "scmax.in" , "r" , stdin ) ;
	freopen ( "scmax.out" , "w" , stdout ) ;
	
	int n , i , j;

	int max = -1 , maxi ;
	
	scanf ( "%d" , & n ) ;
	
	for ( i = 1 ; i <= n ; ++ i )
	{
		scanf ( "%d" , & x[i] ) ;
	}
	
	lung[1]=1;
	
	for ( i = 2 ; i <= n ; ++ i )
	{
		lung[i]=0;
		pred[i]=0;
		for ( j = 1; j < i ; ++ j )
		{
			if ( x[j] >= x[i] ) continue ;
			if ( lung[j] > lung [i] ) 
			{
				lung [i] = lung [j] ;
				pred [i] = j ;
			}
				
		}
		++lung[i];
		if ( max < lung[i] )
		{
			max=lung[i];
			maxi=i;
		}
	}
	printf ( "%d\n" , max ) ;
	
	afis ( maxi ) ;
	
	return 0 ;
	
}