Cod sursa(job #2266551)

Utilizator MariaPanMaria Pan MariaPan Data 22 octombrie 2018 19:20:46
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#define VMAX 100005

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

int a[VMAX], urm[VMAX], lis[VMAX];
int n;

void citire();
void pd(int sufix);
void afisare();
int main()
{
    int i;
    citire();
    urm[n]=0;
    lis[n]=1;
    for (i=n-1; i>=1; i--)
    {
        pd(i);
    }
  /*  for (i=1; i<=n; i++)
        fout<<lis[i]<<' ';
    fout<<'\n';
    for (i=1; i<=n; i++)
        fout<<urm[i]<<' ';
    fout<<'\n';
*/
    afisare();
    return 0;
}

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

void pd(int sufix)
{
    int i, lismax=0, imax;
    if (sufix>0)
        {
            for (i=sufix+1; i<=n; i++)
                 if (a[sufix]<a[i])
                    if (lis[i]>lismax)
                        {lismax=lis[i]; imax=i;}
            if (lismax>0)
                { urm[sufix]=imax;
                 lis[sufix]=1+lismax;
                }
                else
                {
                    lis[sufix]=1;
                    urm[sufix]=0;
                }

        }
    }

void afisare()
{
    int i, nrmax=0, poz, imax;
    for (i=1; i<=n; i++)
        if (lis[i]>nrmax)
           {nrmax=lis[i];
            imax=i;}
    fout<<nrmax<<'\n';
    poz=imax;
    while (nrmax>0)
    {
        fout<<a[poz]<<' ';
        poz=urm[poz];
        nrmax--;
    }
    fout<<'\n';
}