Cod sursa(job #604720)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 24 iulie 2011 18:08:36
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>

#define NMax 100005

using namespace std;

int N, X[NMax], Best[NMax], LMax, iMax;

void Read ()
{
    freopen ("scmax.in", "r", stdin);
    scanf ("%d", &N);
    for (int i=1; i<=N; ++i)
    {
        scanf ("%d", &X[i]);
    }
}

void Print (int i)
{
    if (Best[i]==1)
    {
        printf ("%d ", X[i]);
        return;
    }
    for (int j=i-1; j>0; --j)
    {
        if (X[j]<X[i] and Best[j]+1==Best[i])
        {
            Print (j);
            printf ("%d ", X[i]);
            return;
        }
    }
}

inline int Max (int a, int b)
{
    if (a>b)
    {
        return a;
    }
    return b;
}

int main()
{
    Read ();
    Best[1]=1;
    for (int i=2; i<=N; ++i)
    {
        Best[i]=1;
        for (int j=i-1; j>0; --j)
        {
            if (X[j]<X[i])
            {
                Best[i]=Max (Best[i], Best[j]+1);
            }
        }
        if (Best[i]>LMax)
        {
            LMax=Best[i];
            iMax=i;
        }
    }
    freopen ("scmax.out", "w", stdout);
    printf ("%d\n", LMax);
    Print (iMax);
    return 0;
}