Cod sursa(job #350118)

Utilizator LuffyBanu Lavinia Luffy Data 22 septembrie 2009 19:15:20
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<stdio.h>
#define dim 100001  
using namespace std;
int n,marc[dim],i,j,poz,max,max2,x,mpoz[dim],pozmax;
long long v[dim],a[dim];
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,"%lld",&v[i]);
    max=0;poz=i;
	 for(j=1;j<i;j++)
	  if(marc[j]>max && v[j]<v[i]) {max=marc[j]; poz=j;}
	marc[i]=max+1; mpoz[i]=poz;
    if(marc[i]>=max2) 
		{max2=marc[i]; pozmax=i;}}
  
i=pozmax; j=0;
  while(marc[i]!=1)
  {j++;
   a[j]=v[i];
   i=mpoz[i];}
j++; a[j]=v[i];
  fprintf(g,"%d\n",j);
   
  for(i=j;i>=1;i--)
	fprintf(g,"%lld ",a[i]);
fprintf(g,"\n");

fclose(f);
fclose(g);
return 0;
}