Cod sursa(job #996724)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 12 septembrie 2013 15:55:24
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>

using namespace std;

int n,v[100005],l[100005],next[100005];

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

inline void Solve()
{
    int i,j,p,maxim;
    l[n]=1;next[n]=n+1;
    for(i=n-1;i>=1;i--)
    {
        p=0;maxim=0;
        for(j=i+1;j<=n;j++)
            if(v[j]>v[i] && l[j]>maxim)
            {
                maxim=l[j];
                p=j;
            }
        if(p==0)
        {
            l[i]=1;
            next[i]=n+1;
        }
        else
        {
            l[i]=l[p]+1;
            next[i]=p;
        }
    }
}

inline void Afisare()
{
    ofstream fout("scmax.out");
    int maxim,i,p;
    maxim=l[1];p=1;
    for(i=2;i<=n;i++)
        if(l[i]>maxim)
        {
            maxim=l[i];
            p=i;
        }
    fout<<l[p]<<"\n";
    while(p<=n)
    {
        fout<<v[p]<<" ";
        p=next[p];
    }
    fout<<"\n";
    fout.close();
}

int main()
{
    Read();
    Solve();
    Afisare();
    return 0;
}