Cod sursa(job #2274425)

Utilizator opariucbiancaOpariuc Bianca Gabriela opariucbianca Data 1 noiembrie 2018 19:36:49
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");

int LIS[100005],PREi[100005],n,v[100005],p,maxim;
int main()
{
     int i,j;
    fin>>n;
    for(i=1;i<=n;i++) fin>>v[i];
    LIS[n]=1;
    PREi[n]=-1;
  maxim=1;
  p=n;
  for(i=n-1;i>=1;--i)
   {
   LIS[i]=1;
   PREi[i]=-1;
   for(j=i+1;j<=n;++j)
       if(v[i]<v[j] && LIS[i]<LIS[j]+1)
         {
         LIS[i]=LIS[j]+1;
         PREi[i]=j;
         if(LIS[i]>maxim) maxim=LIS[i],p=i;
         }
   }
   fout<<maxim<<'\n';
   i=p;
   while(i!=-1)
   {
       fout<<v[i]<<' ';
       i=PREi[i];
   }
    return 0;
}