Cod sursa(job #1967038)

Utilizator radumihaisirbuSirbu Radu-Mihai radumihaisirbu Data 15 aprilie 2017 20:17:03
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <cstdio>
using namespace std;
#define NR 100001
FILE *fin=fopen("scmax.in","r");
FILE *fout=fopen("scmax.out","w");
int v[NR],l[NR],p[NR],n,i,L,Max,j;
int main()
{
  fscanf(fin,"%d",&n);
  for (i=1;i<=n;i++)
    {fscanf(fin,"%d",&v[i]);l[i]=1;
      p[i]=-1;}

  for (i=n-1;i>=1;i--)
  {

      for (j=i+1;j<=n;j++)
      {
          if (v[i]<v[j])
            if (l[i]<l[j]+1)
                l[i]=l[j]+1,p[i]=j;

      }

  }
  for (i=1;i<=n;i++)
    if (l[i]>Max) Max=l[i];
 fprintf(fout,"%d\n",Max);
  for (i=1;i<=n;i++)
  {
      if (l[i]==Max) {
        L=1;
        while (L<=Max)
             {fprintf(fout,"%d ",v[i]);i=p[i];
             L++;}
       break;
      }
  }

    return 0;
}