Cod sursa(job #1580883)

Utilizator tudorgalatanRoman Tudor tudorgalatan Data 26 ianuarie 2016 11:33:57
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#define MAX 100001

using namespace std;

ifstream fin  ("scmax.in");
ofstream fout ("scmax.out");

unsigned int N;
unsigned int a[MAX];

unsigned int l[MAX], pos[MAX];
unsigned int Lmax, pos_max;
unsigned int i, j;

void read ();
void solve ();
void print ();

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

void read ()
{
    fin >> N;
    for (i=1; i<=N; i++)
        fin >> a[i];
}

void solve ()
{
    l[N] = 1;
    pos[N] = -1;
    for (i=N-1; i>0; i--)
        for (l[i]=0, pos[i]=-1, j=i+1; j<=N; j++)
            if (a[i] <= a[j] && l[i] < 1+l[j])
            {
                l[i] = 1 + l[j];
                pos[i] = j;
            }
    Lmax = l[1];
    pos_max = 1;
    for (i=1; i<N; i++)
        if (Lmax <= l[i])
        {
            Lmax = l[i];
            pos_max = i;
        }
}

void print ()
{
    fout << Lmax-1 << "\n";
    for (i=pos_max; i!=-1; i=pos[i])
        if (a[i] != a[i-1])
            fout << a[i] << " ";
}