Cod sursa(job #1888144)

Utilizator doriiiiiii7Tirsogoiu Dorina doriiiiiii7 Data 21 februarie 2017 22:34:46
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int i,k,j,L[100005],y[100005],p,ante[100005],x[100005],Lmax,n;
int main()
{
  fin>>n;
  for(i=1;i<=n;i++){
    fin>>x[i];
  }
  for(i=1;i<=n;i++){
    L[i]=1;
    ante[i]=0;
    for(j=1;j<i;j++){
        if(x[i]>x[j]&&L[j]+1>L[i])
        {
            L[i]=L[j]+1;
            ante[i]=j;
        }
    }
    if(L[i]>Lmax){
        Lmax=L[i];
        p=i;
    }
  }
  fout<<Lmax<<"\n";
  k=1; y[1]=p; p=ante[p];
  while(p!=0){
    y[++k]=p;
    p=ante[p];
  }
  for(;k>=1;k--){
    fout<<x[y[k]]<<" ";
  }

  return 0;
}