Cod sursa(job #2386172)

Utilizator BogauuuBogdan Ivancu Bogauuu Data 22 martie 2019 12:28:02
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>

using namespace std;

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

int n,i,maxim,p,j,u,k,v[100002],t[100002],d[100002],af[100002];

int main()
{
    fin >> n;
    for (i=1;i<=n;i++)
    {
        fin >> v[i];
    }
    v[n+1]=2000000005;
    d[1]=1;
    for (i=2;i<=n;i++)
    {
        maxim=0;
        p=0;
        for (j=1;j<i;j++)
        {
            if (v[j]<v[i] && d[j]>maxim)
            {
                maxim=d[j];
                p=j;
            }
        }
        d[i]=maxim+1;
        t[i]=p;
    }
    u=n;
    while (u!=0)
    {
        k++;
        af[k]=v[u];
        u=t[u];
    }
    fout << k << "\n";
    for (i=k;i>=1;i--) fout << af[i] << " ";

    return 0;
}