Cod sursa(job #1610921)

Utilizator pringonGoje Samuel Andrei Daniel pringon Data 23 februarie 2016 20:25:41
Problema Subsir crescator maximal Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>

using namespace std;

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

int n, v[100000], lung[100000], pred[100000];

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

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

void rezolv()
{
    lung[1] = 1;
    int pmax = v[1];
    for(int i=2; i<=n; i++)
    {
        lung[i] = 0;
        for(int 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]>lung[pmax])
            pmax=i;
    }
    out<<lung[pmax]<<"\n";
    subsir(pmax);
}

int main()
{
    in>>n;
    citire();
    rezolv();

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