Cod sursa(job #2192570)

Utilizator firutibogdanFiruti Bogdan-Cristian firutibogdan Data 6 aprilie 2018 15:51:58
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

int main() {

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

  int n, elem, lmax = 1;
  vector<int> val;
  vector<int> dp;
  stack<int> s;

  fin >> n;
  for(int i = 0; i < n; ++i) {
    fin >> elem;
    val.push_back(elem);
    dp.push_back(1);
  }

  for (int i = 0; i < n; ++i) {
    for (int j = i - 1; j >= 0; --j) {
      if (val[i] > val[j] && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1;
      }
    }
    if (dp[i] > lmax) {
      lmax = dp[i];
    }
  }

  fout << lmax << "\n";
  int pos = n - 1;
  while (dp[pos] != lmax) {
    pos--;
  }
  s.push(val[pos]);
  lmax--;
  pos--;

  for(; pos >=0 && lmax > 0; --pos) {
    if (dp[pos] == lmax && val[pos] < s.top()) {
      lmax--;
      s.push(val[pos]);
    }
  }

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

  fin.close();
  fout.close();
  return 0;
}