exercicio de recursao

[cloud460]

O problema é esse:

Considere o problema da subsequencia maxima. Uma versao deste problema

consiste em encontrar a subsequencia crescente de maior comprimento B[1..p] a partir de uma sequencia

A[1..n]. Em outras palavras, B[1..p] e uma subsequencia de A[1..n] se existem indices i1,i2,...,ip tais

que 1 <= i1 < i2 < ...< ip <= n. Por exemplo:

A subsequencia crescente de maior comprimento da sequencia A = (1; 2; 3; 9; 4; 5; 6) é

B =(1; 2; 3; 4; 5; 6).

A subsequencia crescente de maior comprimento da sequencia A = (9; 5; 6; 3; 9; 6; 4; 7) é

B = (5; 6; 6; 7)

Dessa forma, implemente um algoritmo que, atraves de recursao, seja capaz de, dado uma sequencia

de numeros inteiros positivos, encontrar o tamanho da subsequencia crescente de maior comprimento dessa sequencia.

Nao e necessario imprimir os elementos que compoe uma subsequencia de maior comprimento,

apenas o numero de elementos (tamanho) que ela possui.

Aqui vai o meu codigo:

    #include <stdio.h>

int a=-1;
int comp=-1;
int subcresmax(int p[], int tamanho){

    int nelementos=0, i=0, flag=0;
    a++;



    if(tamanho==1){
        nelementos = nelementos++;
        return nelementos;
    }

    if(a<tamanho){

        if(comp<=p[a]){
            comp=p[a];

            nelementos = 1 + subcresmax(p,tamanho);
        }

        else{
            comp=p[a];

            nelementos = subcresmax(p,tamanho);
        }


    }
    return nelementos;
}






int main(){

    int tamanho, i, nelementos;
    int *p;
    scanf("%d\n", &tamanho);

    p = (int*)malloc(tamanho*sizeof(int));
    if(p==NULL){
        printf("Erro de memoria");
        exit(1);
    }

    for(i=0;i<tamanho;i++){
        scanf("%d", &p[i]);
    }

    nelementos = subcresmax(p,tamanho);

    printf("%d\n", nelementos);




    free(p);
    return 0;
}

Se alguem puder me ajudar, agradeço!

Exemplo de uma entrada que esta dando errado : sequencia = (1,2,3,1,1)

Resposta esperada = 3

Resposta que esta dando = 4

[WilkMaia]

A lógica do seu programa está incompleta e com um pequeno erro. Ficaria mais claro de perceber o erro se você estivesse exibindo a subsequência.

Seu programa está tomando a seguinte subsequência, dada a sequência (1, 2, 3, 1, 1):

(1, 2, 3, 1)

Retirando-se a linha

comp=p[a];

de dentro do escopo do else, este problema é corrigido.

Além disso, caso a sequência inicial fosse (4, 5, 1, 2, 3), por exemplo, seu programa falharia em tomar a MAIOR subsequência possível, visto que ele tomaria que a maior subsequência teria início no primeiro elemento, 4.

Tente usar a seguinte abordagem:

[1] Verifique o tamanho da maior subsequência crescente possível começando do primeiro elemento da sequência base (é o que o seu programa faz atualmente). Armazene este valor numa variável à parte (variável maiorSubSeq, por exemplo);

[2] Verifique o tamanho da maior subsequência crescente possível começando do \segundo/ elemento da sequência base. Compare o valor atual com o valor da variável maiorSubSeq. Caso seja maior, armazene-o em maiorSubSeq. Caso contrário, prossiga;

[3] Repita o procedimento [2], com início no elemento seguinte da sequência base;

[4] Repita o procedimento [3], até que você chegue no \K-ésimo/ (posição N, dado N = K-1, do vetor) elemento da sequência base, dado maiorSubSeq > tamanho - N (uma vez que, caso a quantidade de elementos restantes na sequência base seja menor que a quantidade de elementos da maior subsequência encontrada, não há possibilidade de encontrar-se uma subsequência maior).

Boa sorte!