Cod sursa(job #2710927)

Utilizator Mihai_Razvan_IonutMihai Razvan Ionut Mihai_Razvan_Ionut Data 23 februarie 2021 13:40:41
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#define NMAX 100002

using namespace std;

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

int n;
int a[NMAX];
int lgmax[NMAX];
int poz[NMAX];
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()
{
 int i, j;
 lgmax[n]=1; poz[n]=0;
 for (i=n-1; i>0; i--)
     {
     lgmax[i]=1; poz[i]=0;
     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 lg, unde, i;
 lg=0;
 for (i=1; i<=n; i++)
 if (lg<lgmax[i]) {lg=lgmax[i]; unde=i;}
 fout<<lg<<'\n';
 while (unde)
       {
        fout<<a[unde]<<' ';
        unde=poz[unde];
       }
 fout<<'\n';
}