Cod sursa(job #1582940)

Utilizator Paul_StefanescuStefanescu Paul Mihnea Paul_Stefanescu Data 28 ianuarie 2016 17:15:07
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <cstdio>
using namespace std;
int lmax,pmax,lung[100001],v[100001],pred[100001],n;
void refacSir(int p)
{
    if(pred[p]!=0)
        refacSir(pred[p]);
    cout<<v[p]<<' ';
}
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    int i,j;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i];
    lung[1]=1;pmax=1;
    for(i=2; i<=n; i++)
    {
        lmax=0;
        pred[i]=0;
        for(j=1; j<i; j++)
            if(v[j]<v[i])
                if(lung[j]>lmax)
                {
                    lmax=lung[j];
                    pred[i]=j;
                }
        lung[i]=1+lmax;
        if(lung[i]>lung[pmax])
            pmax=i;
    }
    cout<<lung[pmax]<<'\n';
    refacSir(pmax);
    return 0;
}