Cod sursa(job #1582943)

Utilizator filip.dutescuDutescu Filip Ioan filip.dutescu Data 28 ianuarie 2016 17:15:55
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
const int N=100001;
int v[N],lung[N],pred[N],n,lmax;

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

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

    lung[1]=1;
    pmax=1;
    for(int i=2;i<=n;i++){
        lmax=0;
        pred[i]=0;

        for(int 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;
    }

    out<<lung[pmax]<<"\n";
    refacsir(pmax);
    return 0;
}