Cod sursa(job #1338627)

Utilizator andreea.ciobanuCiobanu Andreea andreea.ciobanu Data 10 februarie 2015 10:24:07
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#define DMAX 100001

using namespace std;

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

int a[DMAX], lg[DMAX], urm[DMAX];
int n;

void citire();
void lis();
void afisare();

int main()
{
    citire();
    lis();
    afisare();
    return 0;
}
void citire()
{
    int i;
    fin>>n;
    for (i=1; i<=n; i++)
        fin>>a[i];
}
void lis()
{
    int i, j, maxim, pozmax;
    lg[n]=1;
    urm[n]=0;
    for(i=n-1; i>=1; i--)
        {
        maxim=1;
        pozmax=0;
        for(j=i+1; j<=n; j++)
            if(a[i]<a[j])
                {
                maxim=lg[j]+1;
                pozmax=j;
                }
        lg[i]=maxim;
        urm[i]=pozmax;
        }
}
void afisare()
{
    int i, j, maxim, pozmax;
    maxim=lg[1];
    pozmax=1;
    for(i=2; i<=n; i++)
        if(lg[i]>maxim)
            {
            maxim=lg[i];
            pozmax=i;
            }
    fout<<maxim<<'\n';
    for(i=pozmax; i!=0; i=urm[i])
        fout<<a[i]<<' ';
    fout<<'\n';
}