Cod sursa(job #2554822)

Utilizator s.gabi7Dumitrescu Daniel s.gabi7 Data 23 februarie 2020 14:00:12
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <stdio.h>

int prev[100001];
int main () {
    FILE *fin=fopen ("scmax.in", "r"),
         *fout=fopen ("scmax.out", "w");
    int n;
    fscanf (fin, "%d", &n);

    int v[n+1], maxi[n+1], i, j, maxim=0, tmax=0, last;
    for (i=1; i<=n; i++)
        fscanf (fin, "%d", &v[i]);
    for (i=n; i; i--) {
        maxim=0;
        for (j=i+1; j<=n; j++)
            if (maxi[j]>maxim && v[i]<v[j])
                maxim=maxi[j],
                prev[i]=j;
        maxi[i]=maxim+1;
        if (maxi[i]>tmax)
            tmax=maxi[i],
            last=i;
    }

    fprintf (fout, "%d\n", tmax);
    while (last) {
        fprintf (fout, "%d ", v[last]);
        last=prev[last];
    }
    return 0;
}