Cod sursa(job #809002)

Utilizator alexe.razvanAlexe Razvan alexe.razvan Data 7 noiembrie 2012 19:36:30
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>

using namespace std;

ifstream intrare("scmax.in");
ofstream iesire("scmax.out");

int n;
int v[100];
int lgmax[100], urm[100];
int mmax, ind;

int main()
{
  int i, j;
  intrare >> n;
  
  for(i = 0; i < n; i++)
    intrare >> v[i];
  
  lgmax[n-1] = 1;
  urm[n-1] = -1;
  
  for(i = n - 2; i >= 0; i--)
  {
    lgmax[i] = 1;
    urm[i] = -1;
    for(j = i + 1; j < n; j++)
      if (lgmax[i] < 1 + lgmax[j] && v[i] < v[j])
      {
        lgmax[i] = 1 + lgmax[j];
        urm[i] = j;
      }
  }
  
  for(i = 0; i < n; i++)
    if (lgmax[i] > mmax)
    {
      mmax = lgmax[i];
      ind = i;
    }
  
  iesire << mmax << '\n';
  
  for(i = 0; i < mmax; i++)
  {
    iesire << v[ind] << " ";
    ind = urm[ind];
  }
  
  iesire << '\n';
  iesire.close();
  return 0;
}