Cod sursa(job #1042525)

Utilizator radu2004GOLD radu radu2004 Data 27 noiembrie 2013 09:49:54
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <stdio.h>

using namespace std;
FILE *f,*g;
int n,l[100004],a[100009],i,poz;
long long max1;
void recur (int i,int sum)
{    int j;
  if (sum>1)  for (j=i;j>=1;j--)
    {
        if (sum==l[j]+1 && a[j]<a[i+1])
        {recur (j-1,l[j]);
        fprintf (g,"%d ",a[j]);
        break;}
    }
}
int main()
{f=fopen ("scmax.in","r");

 g=fopen ("scmax.out","w");
 int j;
 fscanf (f,"%d",&n);
 for (i=1;i<=n;i++)
   fscanf (f,"%d",&a[i]);
 for (i=1;i<=n;i++)
 {   max1=0;
     for (j=i-1;j>=1;j--)
     {
         if (a[j]<a[i] && (l[j]+1<l[i] || l[i]==0) && a[j]>max1)
         {

             l[i]=l[j]+1;
         }
      if (a[j]<a[i] && a[j]>max1) max1=a[j];

     }
     if (l[i]==0)
     {
         l[i]=1;


     }
 }
 max1=0;
 for (i=n;i>=1;i--)
 {
     if ( l[i]>max1)
     {
         poz=i;
         max1=l[i];
     }
 }
 fprintf (g,"%d\n",max1);

 recur (poz-1,max1);
 fprintf (g,"%d ",a[poz]);


    return 0;
}