Cod sursa(job #1384614)

Utilizator syna123Andreea Nicoara syna123 Data 11 martie 2015 11:28:29
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>

using namespace std;
ifstream in  ("scmax.in");
ofstream out ("scmax.out");
int lung[1000000],pred[1000000], a[2000000];
void subsir(int p)
{
    if(pred[p]!=0)
    subsir(pred[p]);
    out<<a[p]<<" ";
}
int main()
{
    int pmax,n,i,j,lmax,pr;
    in>>n;
    for(i=1; i<=n; i++)
        in>>a[i];
    lung[1]=1;
    pred[1]=0;
    for(i=2; i<=n; i++)
    {
        lmax=0;
        pr=0;
        for(j=1; j<i; j++)
            if(a[j]<a[i])
                if(lung[j]>lmax)
                {
                    lmax=lung[j];
                    pr=j;
                }
        lung[i]=1+lmax;
        pred[i]=pr;
    }
    pmax = 1;
    for (i = 2; i <= n; i++)
        if (lung[i] > lung[pmax])
            pmax = i;
    out<<lung[pmax]<<" \n";
    subsir(pmax);
    return 0;
}