Cod sursa(job #1294416)

Utilizator danalexandruDan Alexandru danalexandru Data 17 decembrie 2014 15:41:48
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>

using namespace std;

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

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

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

int main()
{
    int n,i,j,maxim=1,lmax;
    f>>n;
    for(i=1; i<=n; i++)
        f>>v[i];
    lung[1]=1;
    for(i=2; i<=n; i++)
    {
        lmax=0;
        for(j=1; j<i; j++)
            if(v[i]>v[j])
                if(lung[j]>lmax)
                {
                    lmax=lung[j];
                    pred[i]=j;
                }
        lung[i]=1+lmax;
        if(lung[i]>lung[maxim])
            maxim=i;
    }
    g<<lung[maxim]<<"\n";
    ssir (maxim);
}