Cod sursa(job #2603733)

Utilizator matthriscuMatt . matthriscu Data 20 aprilie 2020 18:57:06
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include <cstdio>
using namespace std;

int main() {
    int n, i, j, mp,
    v[100005], rez[100005] {}, pred[100005];
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);
    scanf("%d", &n);
    for(i = 1; i <= n; ++i)
        scanf("%d", &v[i]);

    for(i = 1; i <= n; i++)
        for(j = 1; j < i; j++)
            if(v[j] < v[i] && rez[i] < 1 + rez[j]) {
                rez[i] = 1 + rez[j];
                pred[i] = j;
                mp = i;
            }

    for(n = 0; mp; mp = pred[mp])
        rez[++n] = v[mp];

    printf("%d\n", n);
    for(i = n; i >= 1; --i)
        printf("%d ", rez[i]);
}