Cod sursa(job #1438782)

Utilizator CalinSpiridonSpiridon Calin CalinSpiridon Data 20 mai 2015 20:32:27
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n,mx,pm,mxt;
int v[100100],pd[100100];

void afis(int k, int m){
    if(m>0){
        int i=k-1;
        while(pd[i]!=m-1) --i;
        afis(i,m-1);
        fout<<v[k]<<' ';
    }
}


int main(){
    fin>>n;
    for(int i=1;i<=n;++i) fin>>v[i];
    pd[1]=1;
    for(int i=2;i<=n;++i){
        mx=0;
        for(int j=1;j<i;++j)
            if(v[i]>v[j] && pd[j]>mx) mx=pd[j];
        pd[i]=mx+1;
        if(pd[i]>mxt){
            mxt=pd[i];
            pm=i;
        }
    }
    fout<<mxt<<'\n';
    afis(pm,mxt);


    return 0;
}