Cod sursa(job #2446625)

Utilizator LeCapataIustinian Serban LeCapata Data 9 august 2019 21:42:30
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>

using namespace std;

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

int v[100001], d[100001],leg[100001], rez[100001];

int main()
{
    int n;

    in>>n;
    for(int i=1; i<=n; i++)in>>v[i];

    for(int i=1; i<=n; i++)
    {
        d[i]=1;
        for(int j=i-1; j>=1; j--)
        {
            if(v[i]>v[j] && d[j]+1>d[i])
            {
            d[i]=d[j]+1;
            leg[i]=j;
            }
        }
    }

    int mx_len=0, poz=0;
    for(int i=1; i<=n; i++)
        if(d[i]>mx_len)
        {
            mx_len=d[i];
            poz=i;
        }
    out<<mx_len<<'\n';

    while(poz)
    {
    rez[++rez[0]]=v[poz];
    poz=leg[poz];
    }

    for(int i=mx_len; i>=1; i--)
    {
        out<<rez[i]<<" ";
    }

    in.close();
    out.close();
    return 0;
}