Cod sursa(job #2074552)

Utilizator lulian23Tiganescu Iulian lulian23 Data 24 noiembrie 2017 19:22:08
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
#define nmax 123456
#define x first
#define y second
#define endl '\n'

using namespace std;

int v[ nmax ], n, maxx, stop;

pair <int, int> best[ nmax ];

void magie(int x){
    if (x != -1){
        magie(best[ x ].y);
        printf("%d ", v[ x ]);
    }
}

int main(){
    ios_base::sync_with_stdio (false);

    auto ___ = freopen ("scmax.in", "r", stdin);
    ___ = freopen ("scmax.out", "w", stdout);
    assert (___);

    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
        scanf("%d", &v[ i ]);

    best[ 1 ].x = 1;  best[ 1 ].y = -1;

    for (int i = 2; i <= n; i++){
        best[ i ].x = 1;
        best[ i ].y = -1;

        for (int j = 1; j < i; j++)
            if (v[ i ] > v[ j ] && best[ i ].x + 1 > best[ j ].x){
                best[ i ].x = best[ j ].x + 1;
                best[ i ].y = j;

                if (best[ i ].x > maxx){
                    maxx = best[ i ].x;
                    stop = i;
                }
            }
    }
    printf("%d\n", maxx);
    magie( stop );
}