Cod sursa(job #1644864)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 10 martie 2016 09:56:53
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<iostream>
#include<fstream>
#define Nmax 100005

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

int a[Nmax], N, lis[Nmax];

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

void LIS()
{
  int i, j, maxim;
  /// lis[i] = 1 + max(lis[j]), unde j > i si a[j] > a[i]

  for (i=N; i>=1; i--)
  {
     maxim = 0;

     for (j=i+1; j<=N; j++)
     {
          if (lis[j] > maxim && a[j] > a[i])
              maxim = lis[j];
     }
     lis[i] = 1 + maxim;
  }
}


void Afisare()
{
  /// gasim pozitia unde incepe sirul crescator de lung maxima
  int i, j, maxim, poz, gasit;
  maxim = -2;
  for (i=1; i<=N; i++)
  {
    if (lis[i] > maxim)
     {
        poz = i;
        maxim = lis[i];
     }
  }
  /// reconstitui sirul cautand la dreapta lui poz exact *maxim* elemente cu lis[j] == lis[poz] - 1

  fout << maxim << "\n" << a[poz] << " ";

  for (i=2; i<=maxim; i++)
  {
      gasit = 0;
      for (j=poz+1; j<=N && gasit==0; j++)
      {
          if (lis[j] == lis[poz] - 1 && a[j] > a[poz])
             {
                poz = j;
                gasit = 1;
                fout << a[j] << " ";
             }
      }
  }
}

int main ()
{
  Citire();
  LIS();
  Afisare();
  fin.close();
  fout.close();
  return 0;
}