Cod sursa(job #585851)

Utilizator oancea_horatiuOancea Horatiu oancea_horatiu Data 30 aprilie 2011 12:14:26
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<iostream>
#include<fstream>
using namespace std;
int main()
  {
  FILE*d=fopen("scmax.in","r");
  FILE*o=fopen("scmax.out","w");
  long next[100002],a[100002],s[100002],n,i,j,maxt,maxi,max;
  fscanf(d,"%d",&n);
  for(i=1;i<=n;i++) fscanf(d,"%d",&a[i]);
  s[n]=1;maxt=1;
  for(i=n-1;i>0;i--)
    {
      max=0;next[i]=0;
      for(j=i+1;j<=n;j++) if((s[j]>max)&&(a[i]<a[j])) {max=s[j];next[i]=j;};
      s[i]=max+1;
      if(s[i]>maxt) {maxt=s[i];maxi=i;};
    }
  fprintf(o,"%d\n",maxt);
  while(maxi!=0)
    {
      fprintf(o,"%d ",a[maxi]);
      maxi=next[maxi];
    }
  fclose(o);fclose(d);
  return 0;
  }