Cod sursa(job #1333003)

Utilizator SirStevensIonut Morosan SirStevens Data 2 februarie 2015 17:48:06
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int best[100003],a[100003], maxx,sol=0,poz[100003],p,n,j,i;


int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i];
  best[n]=1;
  poz[n]=-1;
  maxx=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]>maxx) maxx=best[i],p=i;
         }
   }
   i=p;
   g<<maxx<<'\n';
  while(i!=-1)
   {
   g<<a[i]<<" ";
   i=poz[i];
   }
    return 0;
}