Cod sursa(job #3221190)

Utilizator Gabriel_DaescuDaescu Gabriel Florin Gabriel_Daescu Data 6 aprilie 2024 11:22:50
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
using namespace std;
ifstream  fin("scmax.in");
ofstream fout("scmax.out");
int N,i,j,l,lmax,L,st,dr,p,q,b[100002],c[100002];
long long v[100002];
int main()
{
    fin>>N;

    for(i=1; i<=N; i++)
    {
        fin>>v[i];
    }

    for(i=N; i>=1; i--)
    {
        lmax=0;
        p=0;
        for(j=i+1; j<=N; j++)
        {
            if(v[i]<v[j] && b[j]>lmax)
            {
                lmax=b[j];
                p=j;
            }
        }

        b[i]=1+lmax;
        c[i]=p;
    }

    L=0;
    for(i=1; i<=N; i++)
    {
        if(b[i]>L)
        {
            L=b[i];
            q=i;
        }
    }

    fout<< L << "\n";

    for(i=q; i!=0; i=c[i])
    {
        fout<< v[i] << " ";
    }

    return 0;
}