Cod sursa(job #3195638)

Utilizator DariusHHanganu Darius DariusH Data 21 ianuarie 2024 13:28:33
Problema Subsir crescator maximal Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

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

#define N_MAX 100000

int v[N_MAX], dp[N_MAX], prevv[N_MAX], arr[N_MAX];

int main()
{
  int n, i, j, maxd, res, respos, pos;
  fin >> n;
  for(i = 0; i < n; ++i) {
    fin >> v[i];
  }
  dp[0] = 1;
  res = 1;
  respos = 0;
  for(i = 1; i < n; ++i) {
    maxd = 0;
    prevv[i] = -1;
    for(j = 0; j < i; ++j) {
      if(v[i] > v[j]) {
        if(dp[j] >= maxd) {
          maxd = dp[j];
          prevv[i] = j;
        }
        maxd = max(maxd, dp[j]);
      }
    }
    dp[i] = maxd + 1;
    if(dp[i] > res) {
      res = dp[i];
      respos = i;
    }
  }

  fout << res << '\n';
  pos = 0;
  while(respos >= 0) {
    arr[pos++] = v[respos];
    respos = prevv[respos];
  }


  for(i = res - 1; i >= 0; --i) {
    fout << arr[i] << ' ';
  }

  return 0;
}