Cod sursa(job #2133604)

Utilizator baranceanuBaranceanu Vlad baranceanu Data 17 februarie 2018 10:26:31
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int a[100000];
int lg[100000];
int urm[100000];
int main()
{
    int i,n,j,maxim,urmatorul,pozmax;
    fin>>n;
    for(i=0;i<n;i++)
        fin>>a[i];
    lg[n-1]=1;
    urm[n-1]=-1;
    for(i=n-2;i>=0;i--)
    {
        maxim=1;
        urmatorul=-1;
        for(j=i+1;j<n;j++)
        {
            if(a[i]<a[j]&&maxim<lg[j]+1)
            {

                maxim=lg[j]+1;
                urmatorul=j;

            }

        }
        lg[i]=maxim;
        urm[i]=urmatorul;
    }
    maxim=lg[0];
    pozmax=0;
    for(i=1;i<n;i++)
    {
        if(lg[i]>maxim)
        {
            maxim=lg[i];
            pozmax=i;
        }
    }
    fout<<maxim<<'\n';
    fout<<a[pozmax]<<' ';
    while(urm[pozmax]!=-1)
    {
        pozmax=urm[pozmax];
        fout<<a[pozmax]<<' ';
    }
    return 0;
}