Cod sursa(job #2133596)

Utilizator stoicageorgeStoica George stoicageorge Data 17 februarie 2018 10:24:05
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#define NMAX 100001
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int a[NMAX], lgmax[NMAX], urm[NMAX], n;
void citire();
void afis();
int main()
{
    int urmator;
    int maxim;
    int i;
    int j;
    citire();
    //dinamica
    //cel mai mic sufix are un element
    lgmax[n-1]=1; urm[n-1]=-1;
    for (i=n-2; i>=0; i--)
    {
        urmator=-1;
        maxim=1;
        for (j=i+1; j<n; j++)
            if (a[i]<a[j] && 1+lgmax[j]>maxim)
            {
                maxim=1+lgmax[j];
                urmator=j;
            }
        lgmax[i]=maxim; urm[i]=urmator;
    }
    //afisare
    //cout<<"da";
    afis();
    return 0;
}
void afis ()
{
    int i;
    int maxim=1, poz=0;
    for (i=0; i<n-maxim; i++)
        if (lgmax[i]>maxim)
        {
            maxim=lgmax[i];
            poz=i;
        }
    fout<<maxim<<'\n';
    fout<<a[poz];
    while (urm[poz]!=-1)
    {
        poz=urm[poz];
        fout<<' '<<a[poz];
    }
    fout<<'\n';
    fout.close();
}
void citire()
{
    int i;
    fin>>n;
    for (i=0; i<n; i++)
        fin>>a[i];
}