Cod sursa(job #2710916)

Utilizator george-rotariuRotariu George george-rotariu Data 23 februarie 2021 13:37:39
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#define NMAX 100002

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

int a[NMAX], lgmax[NMAX], poz[NMAX];
int n;

void citire();
void pd();
void afisare();

int main()
{
 citire();
 pd();
 afisare();
 return 0;
}

void citire()
{
 int i;
 fin>>n;
 for (i=1; i<=n; i++) fin>>a[i];
}

void pd()
{
 lgmax[n]=1; poz[n]=0;
 int i, j;
 for (i=n-1; i>0; i--)
     {
      lgmax[i]=1;
      for (j=i+1; j<=n; j++)
          if (a[i]<a[j])
             if (lgmax[i]<1+lgmax[j])
                {
                 lgmax[i]=1+lgmax[j];
                 poz[i]=j;
                }
     }
}

void afisare()
{
 int p, i, mx=0;
 for (i=1; i<=n; i++)
     if (lgmax[i]>mx)
        {
         mx=lgmax[i];
         p=i;
        }
 fout<<mx<<'\n';
 while (p)
       {
        fout<<a[p]<<' ';
        p=poz[p];
       }
 fout<<'\n';
 fin.close();
 fout.close();
}