Cod sursa(job #895296)

Utilizator mvcl3Marian Iacob mvcl3 Data 27 februarie 2013 10:50:02
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<cstdio>
using namespace std;

const int NMAX = 100009;
int a[NMAX], best[NMAX], n, pre[NMAX], maxim, poz;

int main()
{
    freopen("scmax.in", "rt", stdin); freopen("scmax.out", "wt", stdout);

    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    best[n] = 1;
    pre[n] = n + 1;
    for(int i = n; i > 1; --i)
        for(int j = i - 1; j >= 1; --j)
            if(a[j] < a[i] && best[j] <= best[i])
            {
                best[j] = 1 + best[i];
                if(best[j] > maxim) maxim = best[j], poz = j;
                pre[j] = i;
            }
    printf("%d\n", maxim);
    for(int i = poz; i <= n; i = pre[i])
        printf("%d ", a[i]);

    return 0;
}