Cod sursa(job #357213)

Utilizator bugyBogdan Vlad bugy Data 18 octombrie 2009 14:19:45
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include<stdio.h>
using namespace std;
#define dim 100003

long int a[dim],v[dim],n,i,s,max,j,maxim,nr;      
int best[dim];


int main()
{
	FILE *f=fopen("scmax.in","r"), *g=fopen("scmax.out","w");
	
	
	fscanf(f,"%ld",&n);
	for(i=1;i<=n;i++)
		fscanf(f,"%ld",&a[i]);

	
	for(i=1;i<=n;i++)
		{max=-1;
			for(j=0;j<i;j++)
				if(a[i]>a[j]&&best[j]>max)
					{max=best[j];v[i]=j;}
			
			best[i]=1+max; maxim=best[i];s=i;
		}		
			
		fprintf(g,"%ld\n",maxim);
		nr=0;
		for(i=s;i>=1;i--)
				{best[++nr]=a[i];i=v[i]+1;}
		for(i=nr;i>=1;i--)
		fprintf(g,"%ld ",best[i]);
		fprintf(g,"\n");


fclose(f);
fclose(g);

return 0;}