Cod sursa(job #2261308)

Utilizator RazvanPanaiteRazvan Panaite RazvanPanaite Data 16 octombrie 2018 10:18:15
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
#define InFile "scmax.in"
#define OutFile "scmax.out"
#define DMAX 100010

using namespace std;

FILE *fin=fopen(InFile,"r");
FILE *fout=fopen(OutFile,"w");

int V[DMAX],lis[DMAX],undes[DMAX];
int n;

void citire();
void pd();

int main()
{int i,unde;
 citire();
 pd();
 int maxim=0;
 for(i=1;i<=n;i++)
     if(maxim<lis[i])
        {maxim=lis[i];
         unde=i;
        }
 fprintf(fout,"%d\n",maxim);
 while(unde)
       {fprintf(fout,"%d ",V[unde]);
        unde=undes[unde];
       }
 return 0;
}
void citire()
{int i;
 fscanf(fin,"%d",&n);
 for(i=1;i<=n;i++)
     fscanf(fin,"%d",&V[i]);
}
void pd()
{int i,j,maxim,unde;
 for(i=n;i>=1;i--)
     {maxim=1;
      for(j=i+1;j<=n;j++)
          if(V[i]<V[j] && lis[j]+1>maxim)
             {unde=j;
              maxim=lis[j]+1;
             }
      lis[i]=maxim;
      if(maxim>1)
         undes[i]=unde;
         else
         undes[i]=0;
     }

}