Cod sursa(job #808821)

Utilizator Daniela95Stangaciu Daniela Daniela95 Data 7 noiembrie 2012 13:39:57
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
using namespace std;

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

void citire();
void pd();
void afisare();

int lgmax[100001];
int a[100001];
int urm[100001];
int n;

int main()
{
    citire();
    pd();
    afisare();
    return 0;
}

void citire()
{
fin>>n;
for(int i=1;i<=n;i++)
    fin>>a[i];
}

void pd()
{
lgmax[n]=1;
urm[n]=-1;

int i,j,unde;

for(i=n-1;i>=1;i--)
    {
    int maxim=0;
    unde=-1;
    for(j=i+1;j<=n-1;j++)
        {
        if(a[i]<a[j])
            if(lgmax[j]>maxim)
                {
                maxim=lgmax[j];
                unde=j;
                }
        }
    lgmax[i]=1+maxim;
    urm[i]=unde;
    }
}

void afisare()
{
int i,maxim=0,unde,unde2;

for(i=1;i<=n;i++)
    if(lgmax[i]>maxim)
        maxim=lgmax[i],unde=i;
fout<<maxim<<'\n';

fout<<a[unde]<<' ';

for(i=2;i<=maxim;i++)
    {
    unde=urm[unde];
    fout<<a[unde]<<' ';
    }
}