Cod sursa(job #2252978)

Utilizator TudorMeisterDumitrescu Tudor Constantin TudorMeister Data 3 octombrie 2018 14:38:24
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

long long int n,v[100001],i,l[100001],maxn,j,pmax,val,x,lg;

int main()
{
    fin>>n;
    for (i=1; i<=n; i++) fin>>v[i];
    l[1]=1;

    for (i=2; i<=n; i++)
    {
        maxn=0;
        for (j=i-1; j>maxn; j--)
        {
            if (v[j]<v[i] && l[j]>maxn) maxn=l[j];
        }
        l[i]=maxn+1;
    }

    pmax=1;

    for (i=2; i<=n; i++)
    {
        if (l[i]>l[pmax]) pmax=i;
    }
    val=l[pmax];
    x=pmax;
    while (val>0)
    {
        if (l[x]==val)
        {
            l[x]=-l[x];
            val--;
        }
        x--;
    }

    for (i=x; i<=pmax; i++)
    {
        if (l[i]<0) {lg++;}
    }
    fout<<lg<<'\n';
    for (i=x; i<=pmax; i++)
    {
        if (l[i]<0) {fout<<v[i]<<" ";}
    }
    return 0;
}