Cod sursa(job #1384608)

Utilizator IoanaGavrilescuIoana Gavrilescu IoanaGavrilescu Data 11 martie 2015 11:25:17
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>

using namespace std;

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

int v[100001], lung[100001], pred[100001];

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

int main()
{
    int n, lmax, pr, i, j;

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

    lung[1]=1;
    pred[1]=0;

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

    return 0;
}