Cod sursa(job #1174711)

Utilizator AnduuFMI Alexandru Banu Anduu Data 23 aprilie 2014 18:37:50
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <cstdio>
using namespace std;
int a[100005], l[100005], n;

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 write (int max, int ind) {

    FILE *out = fopen ("scmax.out", "w");
    fprintf (out, "%d\n", max);
    for (int i = ind; i <= n && max; ++i)
        if (l[i] == max) {
            fprintf (out, "%d ", a[i]);
            --max;
        }
    fprintf (out, "\n");
    fclose (out);
}

int main () {

    int max = -1, ind;

    read ();

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

    write (max, ind);

    return 0;
}