Cod sursa(job #929909)

Utilizator IonSebastianIon Sebastian IonSebastian Data 27 martie 2013 12:43:12
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
using namespace std;

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

const int N = 100001;
long long j, i, n, v[N], lung[N], pred[N], lmax, a;

void citire();
void rezolvare();
void subsir(int p);
void afisare();

int main()
{
    citire();
    rezolvare();
    afisare();

    in.close();
    out.close();
    return 0;
}

void citire()
{
    in >> n;
    for(i=1;i<=n;i++)
        in >>v[i];
}

void rezolvare()
{
    for(i=1;i<=n;i++)
    {
        lung[i]=0;
        for(j=1;j<i;j++)
            if(v[j]<v[i])
                if(lung[j]>lung[i])
                {
                    lung[i]=lung[j];
                    pred[i]=j;
                }
        lung[i]++;
        if(lung[i]>lmax)
        {
            lmax=lung[i];
            a=i;
        }
    }
}

void afisare()
{
    out << lmax << "\n";
    subsir(a);
}

void subsir(int p)
{
    if(pred[p]!=0)
        subsir(pred[p]);
    out << v[p] << " ";
}