Cod sursa(job #895354)

Utilizator mvcl3Marian Iacob mvcl3 Data 27 februarie 2013 11:05:23
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 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 - 1; i >= 1; --i)
    {
        if(a[i] < a[i + 1])
        {
            best[i] = best[i + 1] + 1;
            pre[i] = i + 1;
        }
        else
        if(a[i] == a[i + 1])
            if(a[i] < a[pre[i + 1]]) best[i] = 1 + best[pre[i + 1]], pre[i] = pre[i + 1];
        if(maxim < best[i]) maxim = best[i], poz = i;
    }

    printf("%d\n", maxim);
    for(int i = poz; i <= n; i = pre[i])
       printf("%d ", a[i]);

    return 0;
}