Cod sursa(job #1816387)

Utilizator victorpapa98Papa Victor-Alexandru victorpapa98 Data 26 noiembrie 2016 13:50:11
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
# include <cstdio>
# include <algorithm>
using namespace std;

FILE *f = freopen("scmax.in", "r", stdin);
FILE *g = freopen("scmax.out", "w", stdout);

const int N_MAX = 100010;

int v[N_MAX];
int l_max[N_MAX];
int prev_poz[N_MAX];

int n;

int maxim = 0;
int poz_maxim = 0;

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

void solve()
{
    l_max[n] = 1;
    prev_poz[n] = -1;

    for (int i=n-1; i>=1; i--)
    {
        int poz_max = 0;

        for (int j=i+1; j<=n; j++)
        {
            if (v[j] > v[i])
            {
                if (l_max[j] + 1 > l_max[i])
                {
                    poz_max = j;
                    l_max[i] = l_max[j] + 1;
                }
            }
        }

        if (poz_max == 0)
        {
            l_max[i] = 1;
            prev_poz[i] = -1;
        }
        else
        {
            prev_poz[i] = poz_max;
        }

        if (l_max[i] > maxim)
        {
            maxim = l_max[i];
            poz_maxim = i;
        }
    }

    printf("%d\n", l_max[poz_maxim]);

    while (prev_poz[poz_maxim] != -1)
    {
        printf("%d ", v[poz_maxim]);
        poz_maxim = prev_poz[poz_maxim];
    }

    printf("%d ", v[poz_maxim]);
}

int main()
{
    read();
    solve();
    return 0;
}