Cod sursa(job #2107506)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 17 ianuarie 2018 12:55:46
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int N;
int a[100002];
int l[100002];
int pre[100002];
int lgmax;
int pozmax;

int SCMax(int poz)
{
  if(l[poz]>0) return l[poz];

  int j=poz;

  while(a[j]>=a[poz] && j>1)
    --j;

  pre[poz]=j;

  if(j==1)
  {
    l[j]=1;
    return l[j];
  }

  l[poz]=1+SCMax(j);
  return l[poz];
}

void Read()
{
  fin>>N;
  for(int i=1; i<=N; ++i)
    fin>>a[i];

  fin.close();
}

void Do()
{
  int lg;

  for(int i=N; i>=1; --i)
    if(l[i]==0) { lg=SCMax(i);
                  if(lg>lgmax) { lgmax=lg;
                                 pozmax=i;
                               }
                }
}

void Remake(int poz)
{
  if(l[poz]==1) return;

  Remake(pre[poz]);
  fout<<a[poz]<<' ';
}

void Print()
{
  fout<<lgmax<<'\n';
  Remake(pozmax);
  fout<<'\n';

  fout.close();
}

int main()
{
    Read();
    Do();
    Print();

    return 0;
}