Cod sursa(job #1368428)

Utilizator SmitOanea Smit Andrei Smit Data 2 martie 2015 17:17:41
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>

using namespace std;

int n,a[100004],d[100004],predecesor[100004],sol=1,poz1;

inline void Citire()
{
    int i;
    ifstream fin("scmax.in");
    fin>>n;
    for(i=1;i<=n;++i)
        fin>>a[i];
    fin.close();
}

inline void Solutie()
{
    int i,j,maxim,poz;
    d[1]=1;
    for(i=2;i<=n;++i)
    {
        maxim=0;
        poz=0;
        for(j=i-1;j>=2;--j)
        {
            if(d[j]>maxim && a[j]<a[i])
            {
                maxim=d[j];
                poz=j;
            }
        }
        d[i]=1+maxim;
        if(d[i]>sol)
        {
            sol=d[i];
            poz1=i;
        }
        predecesor[i]=poz;
    }
}

inline void Afisare()
{
    int i,k=1;
    ofstream fout("scmax.out");
    fout<<sol<<"\n";
    i=poz1;
    //fout<<a[i]<<" ";
    d[1]=a[i];
    while(predecesor[i]!=0)
    {
        d[++k]=a[predecesor[i]];
        i=predecesor[i];
    }
    for(i=k;i>=1;--i)
        fout<<d[i]<<" ";
    fout<<"\n";
    fout.close();
}

int main()
{
    Citire();
    Solutie();
    Afisare();
    return 0;
}