Cod sursa(job #1384462)

Utilizator rocandu16Badulescu Dan Andrei rocandu16 Data 11 martie 2015 09:33:18
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#define MAX 100001
using namespace std;
int lung[MAX],pred[MAX],v[MAX];
FILE *fout=fopen("scmax.out","w"),*fin=fopen("scmax.in","r");
void sub(int x)
{

if(pred[x]!=0)
    sub(pred[x]);
   fprintf(fout,"%d ",v[x]);
}

int main()
{


    int i,n,lmax,pr,li,j;
    fscanf(fin,"%d",&n);
    for(i=1;i<=n;i++)
    {
      fscanf(fin,"%d",&v[i]);
    }
    lung[1]=1;
    pred[1]=0;
    for(i=2;i<=n;i++)
    {
      lmax=0;
      pr=0;
      for(j=1;j<=i;j++)
      {
        if(v[j]<v[i])
          if(lung[j]>lmax)
            {
              lmax=lung[j];
              pr=j;
            }
      }
      lung[i]=1+lmax;
      pred[i]=pr;
    }
    lmax=0;
    for(i=1;i<=n;i++)
    {
      if(lung[i]>lmax)
        {
          lmax=lung[i];
          li=i;
        }
    }
    fprintf(fout,"%d\n",lmax);
    sub(li);
    return 0;
}