Cod sursa(job #2261395)

Utilizator claraaaSima Clara claraaa Data 16 octombrie 2018 10:46:51
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>

using namespace std;

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

int urm[100005], a[100005], lis[100005];
int n,i,j,maxim,ind,lmax,imax;

int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    urm[n]=0;
    lis[n]=1;
    for(i=n-1;i>=1;i--)
    {
        lmax=0;
        ind=0;
        for(j=i+1;j<=n;j++)
            if(a[i]<a[j]&&lis[j]+1>lmax)
            {
                lmax=lis[j]+1;
                ind=j;
            }
        if(lmax==0)
        {
            lis[i]=1;
            urm[i]=0;
        }
        else
        {
            lis[i]=lmax;
            urm[i]=ind;
        }
        if(lis[i]>maxim)
            maxim=lis[i],imax=i;

    }
    /*for(i=1;i<=n;i++)
        fout<< a[i] << ' ';
    fout<< '\n';
    for(i=1;i<=n;i++)
        fout<< lis[i] << ' ';
    fout<< '\n';
    for(i=1;i<=n;i++)
        fout<< urm[i] << ' ';
    fout<< '\n';*/
    fout<< maxim << '\n';
    fout<< a[imax] << ' ' ;
    i=imax;
    while(urm[i])
    {
        fout<< a[urm[i]] << ' ';
        i=urm[i];
    }
    fout<< '\n';
    return 0;
}