Cod sursa(job #2059102)

Utilizator seby2341Mesca Sebastian seby2341 Data 6 noiembrie 2017 17:30:52
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX=100010;
int n,l[NMAX],v[NMAX],i,aux[NMAX];
void read()
{
    scanf("%lld",&n);
    for (int i=1; i<=n; ++i)
        scanf("%lld", &v[i]);
}
void find_sub()
{
    for (int i=2; i<=n; ++i)
    {
        long long max1=0;
        for (int j=i-1; j>=1; --j)
            if (v[i]>v[j]&& l[j]>max1) max1=l[j];
        l[i]=1+max1;
    }
}
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    read();
    l[1]=1;
    find_sub();
    int imax=0,imin=0;
    int j=1;

    long long max1=0,min1=2100000000;

    for (int i=1; i<=n; ++i)
        if (l[i]>max1) max1=l[i], imax=i;

    long long nrmax=l[imax];
    printf("%lld \n",nrmax);

    int p=nrmax;

aux[1]=v[imax];

    for (int i=imax-1; i>=1; --i)
        if (l[i]==p-1) aux[++j]=v[i],p--;
    for (int i=nrmax; i>=1; --i)
        printf("%lld ",aux[i]);


    return 0;
}