Cod sursa(job #2609575)

Utilizator juniorOvidiu Rosca junior Data 2 mai 2020 22:21:35
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
#define MAX 100001

using namespace std;

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

int n, i, j, maxim, maxi, nr, s[MAX], v[MAX], p, a[MAX];

int main()  {
  fin >> n;
  for (i = 1; i <= n; i++)
    fin >> a[i];
  v[n] = 1;
  for (i = n - 1; i >= 1; i--)  {
    maxim = 0;
    for (j = i; j <= n; j++)  {
      if (a[j] > a[i] && v[j] > maxim)
        maxim = v[j], p = j;
    }
    v[i] = 1 + maxim;
    s[i] = p;
    if (v[i] > maxi)
      maxi = v[i], nr = i;
  }
  fout << maxi << '\n';
  for (i = 1; i <= maxi; i++) {
    fout << a[nr] << ' ';
    nr = s[nr];
  }
}