Cod sursa(job #1088339)

Utilizator serban.cobzacCobzac Serban serban.cobzac Data 20 ianuarie 2014 14:42:29
Problema Subsir crescator maximal Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#define nmax 1001

using namespace std;

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

int n, a[nmax], lg[nmax], prec[nmax], sir[nmax];
int lgmax;

void citire();
void pd();
void constr_sol();
void afisare();

int main(){
    citire();
    pd();
    constr_sol();
    afisare();
    fout.close();
    return 0;
}

void pd(){
    int i, j;
    lg[1]=1; prec[1]=0;
    for(i=2; i<=n; ++i){
        lg[i]=1; prec[i]=0;
        for(j=1; j<i; ++j)
            if(a[j]<=a[i] && lg[j]+1>lg[i]){
                lg[i]=1+lg[j];
                prec[i]=j;
            }
    }
}

void constr_sol(){
    int i, pozmax, crt;
    //aflu lgmax
    lgmax=0;
    for(i=1; i<=n; ++i){
        if(lgmax<lg[i]){
            lgmax=lg[i];
            pozmax=i;
        }
    }
    //construiesc sirul invers
    for(i=pozmax, crt=0; i; ){
        sir[++crt]=a[i];
        i=prec[i];
    }
}

void afisare(){
    int i;
    fout<<lgmax<<'\n';
    for(i=lgmax; i; i--)  fout<<sir[i]<<'\n';
    fout<<'\n';
}

void citire(){
    int i;
    fin>>n;
    for(i=1; i<=n; i++) fin>>a[i];
}