Cod sursa(job #824470)

Utilizator traista.lamaitaTraista traista.lamaita Data 26 noiembrie 2012 17:35:31
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include<fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int lmax[100003],a[100003], maxim,poz[100003],p;
int n,i,j;

int main()
 {f>>n;
  for(i=1;i<=n;++i) f>>a[i];
  lmax[n]=1;
  poz[n]=-1;
  maxim=1; p=n;
  for(i=n-1;i>=1;--i)
   {lmax[i]=1;
    poz[i]=-1;
    for(j=i+1;j<=n;++j)
       if(a[i]<a[j] && lmax[i]<lmax[j]+1)
         {
         lmax[i]=lmax[j]+1;
         poz[i]=j;
         if(lmax[i]>maxim) maxim=lmax[i],p=i;
         }
   }

  g<<maxim<<'\n';
  i=p;
  while(i!=-1) {g<<a[i]<<' '; i=poz[i];}
  g<<'\n';
  return 0;
  }