Cod sursa(job #1860925)

Utilizator minut1Baies Cosmin minut1 Data 28 ianuarie 2017 14:44:23
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>

using namespace std;

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

int lung[100004],pred[100004],i,j,lmax,pmax,v[100004],n;

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

int main()
{
    in >> n;
    for(i=1; i<=n; i++)
        in >> v[i];
    for(i=1; i<=n; i++)
    {
        lmax = 0;
        for(j=1; j<=n; j++)
        {
            if(v[j] < v[i])
            {
                if(lung[j] > lmax)
                {
                    lmax=lung[j];
                    pred[i]=j;
                }
            }
        }
        lung[i] = 1 + lmax;
    }
    pmax = 1;
    for(i=2; i<=n; i++)
    {
        if(lung[i] > lung[pmax])
        {
            pmax = i;
        }
    }
    out << lung[pmax] << "\n";
    sir(pmax);
    return 0;
}