Cod sursa(job #1826425)

Utilizator BlueCodeMihalache Catalin Alexandru BlueCode Data 10 decembrie 2016 14:12:33
Problema Subsir crescator maximal Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int lmax[1000],urm[1000],maxi,n,i,j,pmax,a[1000];
///a-vectorul initial
///lmax[i]-este lungimea sirului  maximal ce se poate forma pornind de la elem i
///urm[i]-este pozitia urmatorului elem dupa a[i] care apare in sirul de lungime maximala

int main()
{  f>>n;
for(i=1;i<=n;i++)
    f>>a[i];
  lmax[n]=1;
  urm[n]=-1;
  for(i=n-1;i>=1;i--)
  {maxi=0;pmax=-1;
  for(j=i+1;j<=n;j++)///daca nu pun egal obtin prima solutie, daca pun egal o obtin pe ultima, ambele fiind optime
  if(a[i]<a[j]&&lmax[j]>=maxi){maxi=lmax[j];pmax=j;}
    ///Daca punem >= obtinem cel mai lung subsir descrescator de lungime maxima
  lmax[i]=1+maxi;urm[i]=pmax;
 }
   pmax=1;
   maxi=lmax[1];
   for(i=2;i<=n;i++)
      if(lmax[i]>maxi){maxi=lmax[i];pmax=i;}
   g<<maxi<<'\n';
   for(i=pmax;i!=-1;i=urm[i])
   g<<a[i]<<" ";
}