Cod sursa(job #2556853)

Utilizator Florinos123Gaina Florin Florinos123 Data 25 februarie 2020 11:23:19
Problema Subsir 2 Scor 47
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>

using namespace std;

ifstream f ("subsir2.in");
ofstream g ("subsir2.out");

int n, val, v[5005], best[5005], sol[5005], lg;

void read ()
{
 int i;
  f >> n;
   for (i=1; i<=n; i++)
   {
      f >> v[i];
      best[i] = 1;
   }
}

void dinamica ()
{
 int i, j, aux, poz, minim = 999999;
  for (i=2; i<=n; i++)
  {
      for (j=1; j<i; j++)
      {
          if (v[j] < v[i])
          {
              aux = best[j] + 1;
               if (aux > best[i])
                 best[i] = aux;
          }
      }
  }

  bool ok;

  for (i=1; i<=n; i++)
  {
     ok = true;
      for (j=i+1; j<=n && ok; j++)
      {
          if (v[j] > v[i])
            ok = false;
      }

     if (ok == true)
     {
         if (v[i] < minim)
         {
             minim = v[i];
             poz = i;
         }
     }
  }
 g << best[poz] << '\n';
 aux = best[poz];
  for (i=poz; i>=1; i--)
  {
      if (best[i] == aux)
      {
          lg ++, sol[lg] = i;
          aux --;
      }
  }

  for (i=lg; i>=1; i--)
    g << sol[i] << " ";
}

int main()
{
read();
dinamica();
    return 0;
}