Cod sursa(job #2876603)

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

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

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

int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i)
    cin >> v[i];
    
  for (int i = n; i >= 1; --i) {
    lg[i] = 1, p[i] = i;
    
    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 != p[pmx]) {
    cout << v[pmx] << " ";
    pmx = p[pmx];
  }
  cout << v[pmx];

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