Cod sursa(job #2074561)

Utilizator lulian23Tiganescu Iulian lulian23 Data 24 noiembrie 2017 19:29:20
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 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, start;

pair <int, int> best[ nmax ];

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[ n ].x = 1;  best[ n ].y = -1;

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

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

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

    while (start != -1){
        printf("%d ", v[ start ]);
        start = best[ start ].y;
    }
}