Cod sursa(job #2511277)

Utilizator cosmin395dimofte cosmin cosmin395 Data 18 decembrie 2019 17:58:11
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
///sol 2

#include <fstream>

using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");
int n,i,j,jm,lgm,lg[100001],a[100001],prec[100001],k,x[100001];
int main()
{
    cin>>n;
    for(i=1; i<=n; i++)
        cin>>a[i];
    ///pas1
    lg[1]=1;
    prec[1]=0;

    for(i=2; i<=n; i++)
    {
        lgm=jm=0;
        for(j=1; j<i; j++)
            if(a[i]>a[j]&&lg[j]>lgm)
            {
                lgm=lg[j];
                jm=j;
            }
            lg[i]=lgm+1;
            prec[i]=jm;
    }
    lgm=0;
    for(i=1;i<=n;i++)
        if(lg[i]>lgm)
    {
        lgm=lg[i];
        jm=i;
    }
    cout<<lgm<<endl;;
    j=jm;
    k=lgm+1;
    do
    {
        k--;
        x[k]=a[j];
        j=prec[j];
    }while(j);
    for(i=1;i<=lgm;i++)
        cout<<x[i]<<' ';

    return 0;
}