Cod sursa(job #1002972)

Utilizator nimeniaPaul Grigoras nimenia Data 29 septembrie 2013 14:32:20
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int main(int argc, char *argv[])
{

  int n;
  f >> n;

  int v[n + 1];
  for (int i = 0; i < n; ++i) {
    f >> v[i];
  }

  int l[n];

  int max_l = 0, max_pos;
  for (int i = 0; i < n; ++i) {
    l[i] = 1;
    for (int j = 0; j < i; ++j) {
      if (v[i] > v[j])
        l[i] = max(l[i], l[j] + 1);
    }
    if (l[i] > max_l) {
      max_l = l[i];
      max_pos = i;
    }
  }

  g << max_l << endl;

  int i = max_pos;
  int last = v[i];
  int last_len = max_l;
  vector<int> sol;
  sol.push_back(last);

  while (last_len > 1) {
    i--;
    if (v[i] < last && l[i] == last_len - 1 ) {
      last = v[i];
      last_len--;
      sol.push_back(last);
    }
  }

  for (int i = (sol.size() - 1); i >= 0; i--) {
    g << sol[i] << " ";
  }

  g << endl;
  return 0;
}