Cod sursa(job #1528159)

Utilizator tudorgalatanRoman Tudor tudorgalatan Data 19 noiembrie 2015 09:55:59
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>

#define NM 100001

using namespace std;

ifstream InF ("scmax.in");
ofstream OutF ("scmax.out");

unsigned a[NM];
unsigned n;

unsigned b[NM];
unsigned i, k, t, maxim;

void scan ();
void solve ();
void print ();

int  main ()
{
    scan ();
    solve ();
    print ();
    return 0;
}

void scan ()
{
    InF >> n;
    for (i=1; i<=n; i++)
        InF >> a[i];
}

void solve ()
{
    b[n] = 1;
    for (k=n-1; k>=1; k--)
    {
        maxim = 0;
        for (i=k+1; i<=n; i++)
            if (a[i] > a[k] && b[i] > maxim)
            maxim = b[i];
        b[k] = maxim + 1;
    }
    maxim = b[i];
    t = 1;
    for (k=1; k<=n; k++)
        if (b[k] > maxim)
        {
            maxim = b[k];
            t = k;
        }
}

void print ()
{
    OutF << maxim << "\n";
    OutF << a[t] << " ";
    for (i=t+1; i<=n; i++)
        if (a[i]>a[t] && b[i]==maxim-1)
        {
            OutF << a[i] << " ";
            maxim--;
        }
}