Cod sursa(job #2177405)

Utilizator BovisioNitica Ionut Bogdan Bovisio Data 18 martie 2018 16:06:49
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>

using namespace std;

int n,a[100001],best[1000001],pos[1000001],leng;

void Read()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%i",&n);
    for(int i=0;i<n;i++)
        scanf("%i",&a[i]);
}

void Dinamic()
{
    pos[n-1] = 0;
    best[n-1] = 0;
    for(int i=n-2;i>=0;i--)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(a[i] < a[j] && best[i] <= best[j])
            {
                best[i] = best[j] + 1;
                pos[i] = j;
            }
        }
    }
}

void Choose(int x)
{
    printf("%i\n",leng);
    while(leng != 0)
    {
        printf("%i ",a[x]);
        x = pos[x];
        leng--;
    }
}

int main()
{
    int pos;
    Read();
    Dinamic();
    leng=1;
    for(int i=n-2;i>=0;i--)
    {
        if(a[i+1] > a[i] && best[i+1] < best[i])
        {
            leng++;
            pos = i;
        }
    }
    Choose(pos);
    return 0;
}