Cod sursa(job #2876635)

Utilizator AndreiV03Andrei Voicu AndreiV03 Data 23 martie 2022 12:56:39
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
using namespace std;

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

int n, v[100001], lg[100001], p[100001], lmx, pmx;

int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i)
    cin >> v[i];
  
  lg[n] = 1, p[n] = -1;
  for (int i = n - 1; i >= 1; --i) {
    lg[i] = 1, p[i] = -1;
    
    for (int j = i + 1; j <= n; ++j)
      if (v[i] < v[j] && lg[i] < lg[j] + 1)
        lg[i] = lg[j] + 1, p[i] = j;
        
    if (lg[i] > lmx)
      lmx = lg[i], pmx = i;
  }
  
  cout << lmx << "\n";
  while (pmx != -1) {
    cout << v[pmx] << " ";
    pmx = p[pmx];
  }

  cin.close();
  cout.close();
  return 0;
}