Cod sursa(job #2130384)

Utilizator jumareastefanstefan jumarea jumareastefan Data 13 februarie 2018 17:37:49
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

long long a[200005], l[200005], maxi, poz, lmax, n, i, j, p[200005], s[200005];

void din()
{
    l[1]=1;
    poz=1;
    lmax=1;
    for (i=2; i<=n; i++)
    {
        l[i]=1;
        p[i]=-1;
        maxi=0;
        for (j=1; j<=i; j++)
        if (a[j]<a[i] && l[j]>maxi)
        {maxi=l[j];
         l[i]=maxi+1;
        p[i]=j;
        if (l[i]>lmax)
        {
            lmax=l[i];
            poz=i;
        }}
    }
}

void afis()
{
    i=poz;
    j=1;
    while (i!=-1)
    {
        //g<<a[i]<<" ";
        s[j]=a[i];
        j++;
        i=p[i];
    }
    reverse (s+1, s+lmax+1);
    g<<lmax<<endl;
    for (i=1 ;i<=lmax; i++)
        g<<s[i]<<" ";
}

int main()
{
    f>>n;
    for (i=1; i<=n; i++)
        f>>a[i];
    din();
   /* for (i=1; i<=n; i++)
        g<<l[i]<<" ";
        for (i=1; i<=n; i++)
            g<<p[i]<<" ";*/
    afis();
}