Cod sursa(job #3195646)

Utilizator SimifilLavrente Simion Simifil Data 21 ianuarie 2024 13:33:47
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");

int main()
{
    int n;
    f >> n;
    int v[n+1];
    int d[n+1];
    int poz[n+1];
    int dmax = 0, pozdmax;
    d[0] = 0;
    poz[0] = 0;
    for( int i = 1; i <= n; ++i )
    {
      f >> v[i];
      int lmax = 0, ind;
      for( int j = i-1; j >= 0; --j )
      {
        if( v[j] < v[i] && d[j] > lmax )
        {
          lmax = d[j];
          ind = j;
        }
      }
      d[i] = lmax+1;
      poz[i] = ind;
      if( dmax < d[i] )
      {
        dmax = d[i];
        pozdmax = i;
      }
    }
    int l = pozdmax;
    g << lmax << endl;
    while( l != 0 )
    {
      g << v[ l ]<< " ";
      l = poz[ l ];
    }
    return 0;
}