Cod sursa(job #1353652)

Utilizator EberardoVladianu Cosmin Eberardo Data 21 februarie 2015 14:32:36
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n,a[100001],m[100001],scm[100001];
#define inf 2000000002
void citire()
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];

}

void rez()
{
    scm[n]=1;
    m[1]=a[n];
    m[0]=inf;
    int lscm=1,val,i;
    for(i=n-1;i;i--)
    {
        int t=lscm;
        while(a[i]>=m[t])
            t--;
        scm[i]=t+1;
        m[scm[i]]=max(m[scm[i]],a[i]);
       if(lscm<scm[i])
            lscm=scm[i];


    }
    fout<<lscm<<endl;
    val=0;
    for(i=1;i<=n;i++)
    {
        if(scm[i]==lscm&&a[i]>val)
        {
            fout<<a[i]<<" ";
            lscm--;
            val=a[i];
        }
    }

}
int main()
{
    citire();
    rez();

    return 0;
}