Cod sursa(job #1020595)

Utilizator cristitamasTamas Cristian cristitamas Data 2 noiembrie 2013 12:17:39
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <cstdio>

using namespace std;

int Sir[100005];
int Best[100005];
int N;
int Smax,Pmax;

void Citire()
{
    scanf("%d\n",&N);
    for(int i=0;i<N;++i)
        scanf("%d ",&Sir[i]);
}

void Rezolvare()
{
    Smax=1;
    Pmax=N-1;
    for(int i=N-1;i>=0;--i)
    {
        Best[i]=1;
        for(int j=i+1;j<N;++j)
            if(Sir[j]>Sir[i] && Best[j]>=Best[i])
                Best[i]=Best[j]+1;
        if(Best[i]>Smax)
        {
            Smax=Best[i];
            Pmax=i;
        }
    }

}

void Afisare()
{
    printf("%d\n",Smax);
    printf("%d ",Sir[Pmax]);
    Smax--;
    int Last=Sir[Pmax];
    for(int i=Pmax+1;i<N;++i)
    {
        if(Best[i]==Smax && Last<Sir[i])
        {
            Smax--;
            Last=Sir[i];
            printf("%d ",Sir[i]);
        }
    }
}

int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    Citire();
    Rezolvare();
    Afisare();
    return 0;
}