Cod sursa(job #2165081)

Utilizator RazvanGutaGuta Razvan Alexandru RazvanGuta Data 13 martie 2018 11:07:04
Problema Subsir crescator maximal Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int best[1003],a[1003], M,sol=0,poz[1003],p;
int n;
void read()
  {
   f>>n;
   for(int i=1;i<=n;++i)
    f>>a[i];
  }
void dinamic()
  {
  int i,j;
  best[n]=1;
  poz[n]=-1;
  M=1;
  p=n;
  for(i=n-1;i>=1;--i)
   {
   best[i]=1;
   poz[i]=-1;
   for(j=i+1;j<=n;++j)
       if(a[i]<a[j]&&best[i]<best[j]+1)
         {
         best[i]=best[j]+1;
         poz[i]=j;
         if(best[i]>M)
            M=best[i],p=i;
         }
   }
  }
void constr()
  {
  int i;
  i=p;
  while(i!=-1)
   {

   g<<a[i]<<" ";
   i=poz[i];
   }
  }
int main()
  {
  read();
  dinamic();
  g<<M<<'\n';
  constr();
  return 0;
  }