Cod sursa(job #488922)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 30 septembrie 2010 16:48:36
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<stdio.h>
#define dim 100100

FILE*f=fopen("scmax.in","r");
FILE*g=fopen("scmax.out","w");

int N,v[dim],nr[dim],max,pozmax,i,j,c[dim],u,sol[dim],k;

inline void afisare () {
	
	fprintf(g,"%d\n",max);
	
	for ( i = k ; i >= 1 ; --i )
		fprintf(g,"%d ",sol[i]);
	
}

int main () {
	
	fscanf(f,"%d",&N);
	
	for ( i = 1 ; i <= N ; ++i )
		fscanf(f,"%d",&v[i]);
	
	for ( i = 1 ; i <= N ; ++i ) {
		max = 0; pozmax = 0;
		
		for ( j = i - 1 ; j >= 0 ; --j ) {
			
			if ( nr[j] > max && v[i] > v[j] )
				max = nr[j],pozmax = j;
			
		}
		
		nr[i] = nr[ pozmax ] + 1 ;
		c[ i ] = pozmax ;
		
	}
	max = 0;
	for ( i = 1 ; i <= N ; ++i )
		if( nr[ i ] > max)
			max = nr[i], u = i;

	while( u != 0 ){
		
		sol[ ++k ] = v[ u ] ;
		u = c[u];
		
	}
	
	afisare();
	
	fclose(f);
	fclose(g);
	
	return 0;
}