Cod sursa(job #2483929)

Utilizator Uriesu_IuliusUriesu Iulius Uriesu_Iulius Data 30 octombrie 2019 15:56:23
Problema Subsir crescator maximal Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int v[100001], lmax[100001];
int n, maxim, pozmax;

void Citire()
{
    int i;
    f>>n;
    for(i=1; i<=n; i++)
        f>>v[i];
    for(i=1; i<=n; i++)
        lmax[i]=1;
}

void Construire()
{
    int i, j;
    for(i=n-1; i>=1; i--)
        for(j=i+1; j<=n; j++)
            if(v[j]>=v[i] && lmax[i]<=lmax[j])
                lmax[i]=lmax[j]+1;
    for(i=1; i<=n; i++)
        if(lmax[i]>maxim)
        {
            maxim=lmax[i];
            pozmax=i;
        }
}

void Afisare()
{
    int i, poz;
    g<<maxim<<endl;
    g<<v[pozmax]<<" ";
    poz=pozmax;
    for(i=pozmax+1; i<=n; i++)
        if(v[i]>=v[poz] && lmax[poz]-lmax[i]==1)
        {
            g<<v[i]<<" ";
            poz=i;
        }
}

int main()
{
    Citire();
    Construire();
    Afisare();
    return 0;
}