Cod sursa(job #2088606)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 15 decembrie 2017 16:32:00
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>
#define in "scmax.in"
#define out "scmax.out"
#define MN 100005
using namespace std;
int N, v[MN], pd[MN], poz[MN], idx;

int main()
{
    assert(freopen(in, "r", stdin));
    assert(freopen(out,"w", stdout));
    assert(scanf("%d", &N));
    for(int i = 1; i <= N; ++i) assert(scanf("%d", v+i));
    pd[N] = 1, poz[0] = 1, idx = N;
    for(int i = N-1; i; --i)
    {
        for(int j = N; j > i; --j)
            if(v[i] < v[j] && pd[i] < pd[j] +1)
                pd[i] = pd[j] +1, poz[i] = j;
        if(pd[i] > pd[0])
        {
            pd[0] = pd[i];
            idx = i;
        }
    }
    int k = 0;
    while(idx)
    {
        pd[++k] = v[idx];
        idx = poz[idx];
    }
    assert(printf("%d\n", k));
    for(int i = 1; i <= k; ++i)
        assert(printf("%d ", *(pd+i)));
    return 0;
}