Cod sursa(job #2964266)

Utilizator 222cezarCezar Stilpeanu 222cezar Data 12 ianuarie 2023 18:56:47
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
using namespace std;

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

int n, x[100001], lung[100002];

void refac_subsirul(int p, int val, int l)
{
  if(l == 1)
  {
    return;
  }
  if(x[p] < val && lung[p] == l - 1)
  {
    refac_subsirul(p - 1, x[p], lung[p]);
    cout << x[p] << ' ';
  }
  else
  {
    refac_subsirul(p - 1, val, l);
  }
}

int main()
{
  cin >> n;
  int pmax = 1;
  for(int i = 1; i <= n; i++)
  {
    cin >> x[i];
    int l_j = 0;
    for(int j = 1; j < i; j++)
    {
      if(x[j] < x[i])
      {
        l_j = max(l_j, lung[j]);
      }
    }
    lung[i] = 1 + l_j;
    if(lung[i] > lung[pmax])
    {
      pmax = i;
    }
  }
  cin.close();

  cout << lung[pmax] << '\n';
  refac_subsirul(pmax, x[pmax] + 1, lung[pmax] + 1);
  cout.close();
  return 0;
}