Cod sursa(job #1804189)

Utilizator rangalIstrate Sebastian rangal Data 12 noiembrie 2016 12:18:43
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
#include <cassert>
#define in "scmax.in"
#define out "scmax.out"
#define N 100003

using namespace std;

int n,v[N],S[N],poz[N],pozmax,Max;

int main()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);

    assert(scanf("%d",&n));

    for(int i=1; i<=n; ++i)
        assert(scanf("%d",&v[i]));
    S[n]=1;
    poz[n]=-1;
    Max=1;
    pozmax=n;

    for(int i=n-1; i; --i)
    {
        poz[i]=-1; //ramane -1 daca nu se gaseste niciun alt element mai mare la dreapta lui v[i]
        int mx=0;
        for(int k=i+1; k<=n; ++k)
            if(v[i]<v[k] && S[k]>mx)
                mx=S[k], poz[i]=k;

        ++mx;
        S[i]=mx;
        if(Max<mx)
        {
            Max=mx;
            pozmax=i;

        }
    }

    printf("%d\n",Max);

    int i;
    for(i=pozmax; i!=-1; i=poz[i])
        printf("%d ",v[i]);
    printf("\n");

    fclose(stdin); fclose(stdout);
    return 0;
}