Cod sursa(job #85345)

Utilizator otilia_sOtilia Stretcu otilia_s Data 21 septembrie 2007 00:35:17
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <stdio.h>
FILE * fin=fopen("subsir2.in","r");
FILE * fout=fopen("subsir2.out","w");
long a[5003];
int b[5003],c[5003];
int n,i,j,max,lmax,poz;
int main()
{
 fscanf(fin,"%d",&n);
 for (i=1;i<=n;i++)
  fscanf(fin,"%ld",&a[i]);
 fclose(fin);
 lmax=0;
 for (i=n;i>=1;i--)
  {
   max=0; c[i]=0;
   for (j=i+1;j<=n;j++)
    if (a[j]>=a[i])
       if (b[j]>max) {max=b[j]; c[i]=j;} else
       if (b[j]==max) if (a[c[i]]>a[j]) {c[i]=j;}
   b[i]=1+max;
   if (b[i]>lmax) {lmax=b[i]; poz=i;} else
   if (b[i]==max&&a[i]<=a[poz]) poz=i;
  }
 fprintf(fout,"%d\n",lmax);
 while (poz)
  {
   fprintf(fout,"%d ",poz);
   poz=c[poz];
  }
 fclose(fout);
return 0;
}