Cod sursa(job #895477)

Utilizator pintilie.andreiPintilie pintilie.andrei Data 27 februarie 2013 11:33:30
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
//subsir crescator maximal.
//determinati un subsir a lui a crescator
//a[i1]<=a[i2]<=...<=a[ik];
//de lungime maxima

//a(a1,a2,...,an)
//subsir a[i1],a[i2],...a[ik], i1<i2<...<ik
//subsecventa-formata din elmente consecutive. a[i],a[i+1],a[i+k];

#include <fstream>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");
//subprobleme. sa se det cel mai lung subsir crescator care incepe la pozitia i;
///notam lgmax[i]= lung celui mai lung subsir cresc.
//urm[i]=pozitia elem care urmeaza dupa a[i] in cel mai lung subsir cresc.
//-1 daca nu exista urmatorul.

int n,i,a[100010],urm[100010],lgmax[100010],maxim,j,jmax;

int main()
{
    fin >> n;
    for(i=1;i<=n;i++)
        fin >> a[i];
    lgmax[n]=1;
    urm[n]=-1;
    for(i=n-1;i>=1;i--)
    {
        maxim=0;jmax=0;
        for(j=i+1;j<=n;j++)
            if(a[i]<a[j])
            if(lgmax[j]>maxim)
                maxim=lgmax[j],jmax=j;
        lgmax[i]=1+maxim;
        if(jmax!=0)
            urm[i]=jmax;
        else urm[i]=-1;
    }
    maxim=0;
    for(i=1;i<=n;i++)
        if(lgmax[i]>maxim)
            maxim=lgmax[i],jmax=i;
    fout << maxim << '\n';
    int x;
    x=jmax;
    for(i=1;i<=maxim;i++)
    {
        fout << a[x] << ' ';
        x=urm[x];
    }
    return 0;
}