Cod sursa(job #610875)

Utilizator PatrikStepan Patrik Patrik Data 29 august 2011 15:39:15
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
	#include<stdio.h>
	#define MAX 100001
	FILE *f , *g ;
	long n , v[MAX] , poz[MAX] , lg[MAX] , max , p ;
	
	void read();
	void solve();
	void tipar( );
	
	int main()
	{
		read();
		solve();
		tipar();
		return 0;
	}
	
	void read()
	{
		f=fopen("scmax.in" , "r");
		fscanf(f , "%ld" , &n );
		for ( long  i = 1 ; i<= n ; ++i )
			fscanf(f , "%ld" , &v[i] );
		fclose(f);
	}
	
	void solve()
	{
		lg[n] = 1;
		for (long i = n-1 ; i ; i-- )
		{
			lg[i] = 1;
			for ( long j = i+1 ; j <= n ; ++j )
				if(v[i]< v[j] && 1 + lg[j] > lg[i] )
				{
					lg[i] = 1 + lg[j] ;
					poz[i] = j ;
					if(lg[i] > max )
					{
						max = lg[i] ;
						p = i ;
					}
				}
		}
	}
	
	void tipar()
	{
		g=fopen("scmax.out" , "w" );
		fprintf(g , "%ld\n"  , max);
		while(p)
		{
			fprintf(g , "%ld " ,  v[p] );
			p = poz[p] ;
		}
		fclose(g);
	}