Cod sursa(job #554588)

Utilizator laurionLaurentiu Ion laurion Data 14 martie 2011 23:01:29
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<cstdio>
#include<fstream>
#include<cstring>
int main()
{
    std::ifstream fin("scmax.in");
    std::ofstream fout("scmax.out");

    int n,v[100010];

    fin>>n;
    int i,j;
    for(i=0;i<n;++i)
    {
        fin>>v[i];
    }

    int m[100010],poz[100010];
    memset(poz,0xff,sizeof(poz));
    //memset(m,0,sizeof(m));
    int max=0,pozmax=0;
    for(i=n-1;i>=0;--i)
    {
        m[i]=1;
        for(j=i+1;j<n;++j)
        {
            if(v[i]<v[j] && m[i]<m[j]+1)
            {
                m[i]=m[j]+1;
                poz[i]=j;
            }
        }
        if(max<m[i])
        {
                max=m[i];
                pozmax=i;
        }
    }
    fout<<max<<'\n';

    for(i=pozmax;i!=-1;i=poz[i])
    {
        fout<<v[i]<<' ';
    }
    fout<<'\n';
}