Cod sursa(job #1144624)

Utilizator AnduuFMI Alexandru Banu Anduu Data 17 martie 2014 13:01:20
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
using namespace std;

int a[101], n, l[101], max, savei;

void read () {

    FILE *in = fopen ("scmax.in", "r");

    fscanf (in, "%d", &n);
    for (int i = 1; i <= n; ++i)
        fscanf (in, "%d", &a[i]);

    fclose (in);
}

void solve () {

    l[n] = 1;
    for (int i = n - 1; i >= 1; --i) {
        for (int j = i + 1; j <= n; ++j)
            if (a[i] <= a[j] && l[i] <= l[j])
                l[i] = l[j] + 1;
        if (!l[i])
            l[i] = 1;
        if (l[i] > max) {
            max = l[i];
            savei = i;
        }
    }
}

void write () {

    int b;
    FILE *out = fopen ("scmax.out", "w");

    fprintf (out, "%d\n", max);

    b = a[savei];
    for (int i = savei; max; ++i)
        if (a[i] >= b && max == l[i]) {
            fprintf (out, "%d ", a[i]);
            --max;
            b = a[i];
        }
}

int main()
{
    read ();
    solve ();
    write ();

    return 0;
}