Cod sursa(job #2672905)

Utilizator cristiemanuelstroe cristian emanuel cristiemanuel Data 15 noiembrie 2020 13:27:28
Problema Subsir crescator maximal Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include  <iostream>
#include  <fstream>

using namespace std;

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

const int Nmax = 1e5 + 5;
int L[Nmax],
    V[Nmax],
    Next[Nmax],
    n;

int main()
{
  in>>n;
  for(int i = 1; i <= n; i++)
    in>>V[i];
  L[n] = 1;
  Next[n] = -1;
  for(int i = n - 1; i > 0; i--)
  {
    L[i] = 1, Next[i] = -1;
    for(int j  = i + 1; j <= n ; j++)
      if(V[i] <= V[j] && L[j] + 1 > L[i])
      {
        //L[i] = max(L[j]+1, L[i]);
        L[i] = L[j] + 1;
        Next[i] = j;
      }
  }
  int pMax = 1;
  for(int i = 1; i <= n; i++)
    if(L[pMax] < L[i])
     pMax = i;
  out<<L[pMax]<<'\n';
  int k = pMax;
  for(; k != -1;out<<k<<' ',k = Next[k]);
  return 0;
}