Cod sursa(job #2007928)

Utilizator costi2Radu Canu costi2 Data 4 august 2017 16:13:00
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stdio.h>

using namespace std;

#define Nmax 100001

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

vector<int> vec;
int sol[Nmax],path[Nmax];

void print(int pos,int max ,int nivel)
{
  if(max < nivel)
    return;
  print(path[pos],max,nivel+1);
  out << vec[pos] << ' ';
}
void solve(int dim)
{
  sol[0] = 1;
  int max = -Nmax;
  int position = -1;
  for(int i = 1;i < dim;i++)
  {
    sol[i] = 1;
    for(int j = 0; j < i; j++)
    {
      if(vec[i] > vec[j] && sol[i] < sol[j] + 1)
      {
        sol[i] = sol[j] + 1;
        path[i] = j;
        if(max < sol[i])
        {
          max = sol[i];
          position = i;
        }
      }
    }
  }
  int nivel = 1;
  out << max << '\n';
  print(position,max,nivel);

}

int main()
{
  int DIM,aux;
  in >> DIM;
  for(int i = 0;i < DIM;i++){
    in >> aux;
    vec.push_back(aux);
  }
  solve(DIM);
  return 0;
}