Cod sursa(job #2218070)

Utilizator Iulia25Hosu Iulia Iulia25 Data 3 iulie 2018 12:05:58
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <fstream>

using namespace std;

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

const int maxn = 100001;
int n, a[maxn], b[maxn], bef[maxn];
int maxim, maxi, k;

int main()  {
  fin >> n;
  for (int i = 1; i <= n; ++i)  {
    fin >> a[i];
    for (int j = i - 1; j; --j)  {
      if (a[j] < a[i] && b[j] >= b[i])  {
        b[i] = b[j] + 1, bef[i] = j;
        if (b[i] > maxim)
          maxim = b[i], maxi = i;
      }
    }
  }
  fout << ++maxim << '\n';
  while (maxi)  {
    b[++k] = a[maxi];
    maxi = bef[maxi];
  }
  for (int i = maxim; i; --i)
    fout << b[i] << ' ';
}