Cod sursa(job #560336)

Utilizator mvbinfoDragos Dinca mvbinfo Data 18 martie 2011 14:05:58
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<stdio.h>
#define dim 100005
using namespace std;

int pre[dim],n,i,j,ii,nr;
long int best[dim],v[dim],max;


int main()
{
	FILE *f=fopen("scmax.in","r"), *g=fopen("scmax.out","w");
	
	
fscanf(f,"%d ",&n);

for(i=1;i<=n;i++)
{
	fscanf(f,"%ld",&v[i]);
		
	for(j=i-1;j>=1;j--)
		if(v[j]<v[i] && best[j] +1 > best[i])
			{best[i]=best[j] +1 ;
			pre[i]=j;}
		
	if(!best[i])
		{best[i]=1;	pre[i]=0;}
	if(best[i] > max)
	{
		max=best[i];
		ii=i;	
	}
}
fprintf(g,"%d\n",max);
do
{
	//fprintf(g,"%d ",v[ii]);
	best[++nr]=v[ii];
	ii=pre[ii];
}while(pre[ii]!=0);

//fprintf(g,"%d \n",v[ii]);
best[++nr]=v[ii];

for(i=nr;i>=1;i--)
	fprintf(g,"%d ",best[i]);

fprintf(g,"\n");

fclose(f);
fclose(g);

return 0;
}