Cod sursa(job #3167066)

Utilizator Horia123144Musat Horia Gabriel Horia123144 Data 9 noiembrie 2023 22:23:40
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n ,D[100005],v[100005],verif[100005],sol,primul,ultimul,maxi;
void constructiedrum(int u)
{
    if(u!=0)
    {
        constructiedrum(verif[u]);
        fout<<v[u]<<' ';
    }
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    D[1]=1;
    for(int i=2;i<=n;i++)
    {
        maxi=0;
        for(int j=1;j<=i;j++)
            if(v[j]<v[i] && D[j]>maxi)
        {
            maxi=D[j];
            primul=j;
        }
        D[i]=maxi+1;
        if(D[i]!=1)
            verif[i]=primul;
        else
            verif[i]=0;
        if(D[i]>sol)
        {
            sol=D[i];
            ultimul=i;
        }
    }
    fout<<sol<<'\n';
    constructiedrum(ultimul);
    return 0;
}