Cod sursa(job #1430823)

Utilizator Neculoiu_Marius_323CBNeculoiu Marius Neculoiu_Marius_323CB Data 8 mai 2015 21:03:34
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#define MAX 101

using namespace std;


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



int A[MAX] ;
int  N,poz;
int best[MAX];
int pre[MAX];
int maxim;
void dinamica(){

    int  i,j ;


    best[N] = 1;
    pre[N] = -1;
    maxim =1;
    poz =N;
    for(i = N -1 ; i >= 0 ; i--){
        best[i] = 1 ;
        pre[i] = -1;
        for(j = i + 1 ; j <=N ; ++j ){

            if(A[j] < A[i] && best[i] < 1 + best[j] ){
                best[i] = 1 + best[j];
                pre[i] = j;
                if(best[i] > maxim ){
                    maxim = best[i];
                    poz = i;
                }
            }

        }

    }

}
void construieste(){
 int i;
 i = poz;

 while(i!=-1)
    {
     fout<<A[i]<<"\n";
     i = pre[i];

    }

}
int main()
{

    fin>>N;
    for(int i = 0 ; i < N ;i++){

        fin>>A[i];
    }
    dinamica();
    fout<<maxim<<"\n";
    construieste();
    return 0;
}