Cod sursa(job #1408148)

Utilizator VladuZ1338Vlad Vlad VladuZ1338 Data 29 martie 2015 20:37:22
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
#define nmax 100005

using namespace std;

int n, i, j, k, h, maxi, maxi2, maxi3, v[nmax], pre[nmax], sol[nmax], b[nmax];

int main()
{
    freopen ("scmax.in", "r", stdin);
    freopen ("scmax.out", "w", stdout);
    scanf ("%d", &n);
    for (i=1; i<=n; i++) scanf ("%d", &v[i]);
    for (i=1; i<=n; i++)
    {
        maxi=0;
        for (j=1; j<=i; j++)
        {
            if (v[j]<v[i]) if (b[j]>maxi) {maxi=b[j]; k=j;}
        }
        if (maxi)
        {
            b[i]=b[k]+1;
            pre[i]=k;
        }
        else b[i]=1;
    }
    for (i=1; i<=n; i++)
    {
        if (b[i]>maxi2) {maxi2=b[i]; maxi3=i;}
    }
    i=maxi3;
    while (pre[i])
    {
        sol[++h]=v[i];
        i=pre[i];
    }
    sol[++h]=v[i];
    printf ("%d\n", maxi2);
    for (i=h; i>=1; i--) printf ("%d ", sol[i]);
}