Cod sursa(job #902952)

Utilizator DanFodorFODOR Dan Horatiu DanFodor Data 1 martie 2013 17:39:16
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>

using namespace std;

int n, i, a[100069], l[100069], ne[10006];

int main()
{
    freopen ("scmax.in", "r", stdin);
    freopen ("scmax.out", "w", stdout);\
    scanf ("%d", &n);
    for (i=1; i<=n; i++)
        scanf ("%d ", &a[i]);
    l[n]=1;
    int k, poz, maxi;
    for (k=n-1; k>0; k--)
    {
        maxi=0, poz=n+1;
        for (i=k+1; i<=n; i++)
        {
            if (a[k]<a[i] && l[i]>maxi)
            {
                maxi=l[i];
                poz=i;
            }
        }
        if (poz!=n+1)
        {
            l[k]=maxi+1;
            ne[k]=poz;
        }
        else
            l[k]=1;
    }
    maxi=0;
    for (i=1; i<=n; i++)
        if (maxi<l[i])
        {
            maxi=l[i];
            poz=i;
        }
    printf ("%d\n", maxi);
    while (ne[poz])
    {
        printf ("%d ", a[poz]);
        poz=ne[poz];
    }
    printf ("%d", a[poz]);

    return 0;
}