Cod sursa(job #929873)

Utilizator heracleRadu Muntean heracle Data 27 martie 2013 12:23:53
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>

using namespace std;
ifstream in ("scmax.in");
ofstream out ("scmax.out");

const int OS=100001;
int v[OS],lung[OS],pred[OS];


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

}

int main()

{
    int n,i,j,max=0,imax,vmax,max0;
    in>>n;
    for(i=1;i<=n;i++)
        in>>v[i];
    for(i=1;i<=n;i++)
    {
        lung[i]=0;
        for(j=1;j<i;j++)
            if(v[j]<v[i] && lung[j]>lung[i])
                {
                    lung[i]=lung[j];
                    pred[j]=i;
                }
        lung[i]++;
        if(lung[i]>max)
        {
            max=lung[i];
            imax=i;
            vmax=v[i];
        }
    }
    out<<max;


        subsir(imax);
    return 0;
}