Cod sursa(job #2608755)

Utilizator ValentinStStamate Valentin ValentinSt Data 1 mai 2020 18:28:32
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;

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

int main() {

  int n, *v, *d;
  in>>n;
  v = new int[n + 1];
  d = new int[n + 1];

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

  d[1] = 1;

  int maxLen = 0;
  for (int i = 2; i <=n; i++) {
    d[i] = 0;
    for (int j = i - 1; j >= 1; j--) {
      if (v[j] < v[i]) {
        d[i] = max(d[i], d[j]);
      }
    }
    d[i]++;
    if (maxLen < d[i]) {
      maxLen = d[i];
    }
  }

  out<<maxLen<<"\n";

  stack<int> s;

  
  int tempLen = maxLen;
  int lastEl;
  int i;
  for (i = n; i >= 1; i--) {
    if (d[i] == tempLen) {
      lastEl = v[i];
      s.push(v[i]);
      tempLen--;
      break;
    }
  }

  for (; i >= 1; i--) {
    if (d[i] == tempLen && v[i] < lastEl) {
      tempLen--;
      lastEl = v[i];
      s.push(v[i]);
    }
  }

  while (!s.empty()) {
    out<<s.top()<<" ";
    s.pop();
  }

  return 0;
}