Cod sursa(job #3329224)

Utilizator DariusJohnDarius Dumitrescu DariusJohn Data 12 decembrie 2025 12:27:31
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int main() {
  int n, ans = 0, val;
  fin >> n;
  vector<pair<int, int>> dp;
  vector<int> output;
  for (int i = 0; i < n; i++) {
    int x;
    fin >> x;
    int maxRec = 0;
    for (int j = 0; j < dp.size(); j++) {
      if (dp[j].second < x && dp[j].first > maxRec)
        maxRec = dp[j].first;
    }
    dp.push_back({maxRec + 1, x});
    if (maxRec + 1 > ans) {
      ans = maxRec + 1;
      val = x;
    }
  }
  fout << ans << "\n";

  for (int i = dp.size() - 1; i >= 0; i--) {
    if (dp[i].first == ans && dp[i].second <= val) {
      output.push_back(dp[i].second);
      ans--;
      val = dp[i].second;
    }
  }
  for (int i = output.size() - 1; i >= 0; i--)
    fout << output[i] << " ";
}