Cod sursa(job #628507)

Utilizator wefgefAndrei Grigorean wefgef Data 1 noiembrie 2011 16:46:01
Problema Subsir crescator maximal Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
using namespace std;

const int MAX_N = 1024;

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

int n;
int v[MAX_N];
int d[MAX_N];

void read() {
  fin >> n;
  for (int i = 1; i <= n; ++i)
    fin >> v[i];
}

void write_solution(int pos) {
  if (pos == 0) return;
  for (int i = 0; i < pos; ++i)
    if (v[i] < v[pos] && d[i] == d[pos] - 1) {
      write_solution(i);
      fout << v[pos] << " ";
      return;
    }
}

void solve() {
  for (int i = 1; i <= n; ++i) {
    d[i] = 1;
    for (int j = 1; j < i; ++j)
      if (v[j] < v[i] && d[j] + 1 > d[i])
        d[i] = d[j] + 1;
  }

  // find max length
  int best = 0, pos = -1;
  for (int i = 1; i <= n; ++i)
    if (d[i] > best) {
      best = d[i];
      pos = i;
    }
  
  fout << best << "\n";
  write_solution(pos); 
}

int main() {
  read();
  solve();
}