C algoritmo de kadane / subarray/ vetor contiguo de soma maxima

[nagatonie]

Oi pessoal, feliz ano novo p vcs!

 

Estou estudando o algoritmo de kadane em c, mas não consigo resolver um porém. Criei um código onde ele lê o valor de soma máxima e mínima, mas o objetivo é adicionar uma subsequência de k elementos de L, com maior e menor somatórios do vetor. 

por exemplo:

L = { -2, 3, 4 , 1, 2, -1}

K = 2

maior somatorio: { 4, 1} = 5

menor somatorio = { -2, 3} = 1 (primeira) | {2, -1} = 1 (ultima)

A minha única dúvida é ler a subsequência do K, pois o código que fiz pega o maior somatório e o menor somatório de todo o L. 

for(i = 0; i < n; i++) {  // n = tamanho da sequencia de l (que é digitada posteriormente pelo usuário)

        max_atual += l[i];
    
        if(max_atual < 0 ){
            max_atual = 0;
        }
        if (max_atual > max) {
            max = max_atual;
        }
    }
    
    for(i = 0; i < n; i++){
        
        min_atual += l[i];
        if(min_atual > 0 ){
            min_atual = 0;
        }
        if (min_atual < min) {
            min = min_atual;
        }
    
    }
    

Poderiam me dar uma luz?

[RPGStreamer]

Acho que a solução tá em dividir o vetor em pedaços iguais a k (passando k como n às funcões de menor soma e maior soma), e ir atualizando a menor e maior soma conforme caminha pelo vetor (indo de 0 a k, depois de 1 a k + 1, depois de 2 a k + 2, etc, até k + x == n. k não pode ser maior que o tamanho do vetor, e não pode ser menor que 2.

[nagatonie]

@RPGStreamer Essa é minha dúvida real, não consigo fazer a manipulação do vetor. Alguma dica?

[JorgeGus]

Em 06/01/2022 às 11:24, nagatonie disse:

L = { -2, 3, 4 , 1, 2, -1}

K = 2

maior somatorio: { 4, 1} = 5

Isso está certo? Não deveria ser

maior somatorio: { 3, 4} = 7 ?

 

E K vai ser informado pelo usuário?

[nagatonie]

@JorgeGus isso, k sendo informado pelo usuário.
como k =2, o sistema verifica o maior somatorio em grupo de 2, ex: -2, 3; 4, 1; 2, -1;

 

[JorgeGus]

Você vai ter que percorrer o vetor 2 vezes, primeiro para encontrar a maior e menor soma, e depois para exibir as sequências que formam k.

 

Primeiro use um for para somar os k primeiros elementos de L e atribua a soma para o maior e o menor valor.

 

Crie um for de 1 até (número de elementos de L) - k ;

 

Dentro desse for crie outro for, de 0 até menor que k;

 

Nesse for some os valores de L usando como índice o contador do primeiro for + o contador do segundo for;

 

Verifique se a soma é maior ou menor que os valores anteriores, se forem, faça a substituição;

 

Encerre o for e atribua 0 à soma.

 

Depois é só repetir o processo, mas exibindo as sequências.

 

 

 

[nagatonie]

@JorgeGus Deixa eu ver se entendi, seria mais ou menos isso?

for(j = 1; j < n - k; j++){
        for(z=0; 0 < k; z++){
            value = l[j] + l[z];
        }
    }

 

[JorgeGus]

@nagatonie "j < n - k" seria "j <= n - k" e a soma está errada.

for (j = 1; j <= n - k; j++){
	for (z = 0; 0 < k; z++){
            value += l[j + z];
	}
	printf("%d ", value);
	value = 0;
}

Esse código deve exibir a partir da segunda combinação, já que a primeira vai ser somada separadamente antes para ser atribuída à maior e à menor soma.

 

Essa solução parece funcionar corretamente.

[nagatonie]

@JorgeGus fiz a primeira parte para a soma assim:

for(i=0; i < k; i++)
        res += l[i];

    max_atual = res;
    for(i = k; i < n; i++){
        max_atual += l[i] - l[i - k];
        if (res > max_atual){
            res = res;
        } else{
            res = max_atual;
        }

 

quando adiciono essa segunda parte,

for (j = 1; j <= n - k; j++){
	for (z = 0; 0 < k; z++){
            value += l[j + z];
	}

para exibir as sequencias que formam k, meu compilador fecha e não compila

[JorgeGus]

1 hora atrás, nagatonie disse:

@JorgeGus fiz a primeira parte para a soma assim:

for(i=0; i < k; i++)
        res += l[i];

    max_atual = res;
    for(i = k; i < n; i++){
        max_atual += l[i] - l[i - k];
        if (res > max_atual){
            res = res;
        } else{
            res = max_atual;
        }

 

quando adiciono essa segunda parte,

for (j = 1; j <= n - k; j++){
	for (z = 0; 0 < k; z++){
            value += l[j + z];
	}

para exibir as sequencias que formam k, meu compilador fecha e não compila

Não entendi o seu código, o fato de estar subtraindo elementos em um algoritmo em que deveria haver apenas a comparação de somas não faz sentido pra mim.

[nagatonie]

@JorgeGus não entendi. essa primeira parte eu fiz para pegar a maior soma dos elementos em k. como você fez?

[JorgeGus]

3 horas atrás, nagatonie disse:

não entendi. essa primeira parte eu fiz para pegar a maior soma dos elementos em k. como você fez?

É só substituir o printf pela comparação, o objetivo desse código como eu disse era gerar as somas.

[nagatonie]

@JorgeGus Pode me mostrar seu código?

Não consigo mostrar os maiores somatórios como o seu:

20 horas atrás, JorgeGus disse:

minha saída:

[JorgeGus]

@nagatonie Não teria sentido postar o programa pronto aqui, mas depois de descobrir a maior e menor soma, basta percorrer novamente as combinações, mas no lugar de verificar se a soma é maior ou memor que os valores anteriores você verifica se são iguais ao maior ou menor valor que já foi definido, e exibe a combinação que gerou os valores. E você vai ter que repetir isso 2 vezes uma para a maior e outra a menor soma, para que as combinações não saiam misturadas.

[nagatonie]

@JorgeGus não estou conseguindo fazer desse jeito. Eis minha última tentativa:

não consigo fazer com que meu código mostre somente a subsequência de maior soma. ficou assim

[Ansi C]

Em 06/01/2022 às 11:24, nagatonie disse:

L = { -2, 3, 4 , 1, 2, -1}

Em 06/01/2022 às 11:24, nagatonie disse:

maior somatorio: { 4, 1} = 5

Para k = 2, mas nosso cérebro nos diz que k pode ser 4 e o maior somatório {3, 4, 1, 2} = 10.

 

Vejam agora, eu sei que k começa com 2 e a "soma móvel" se desloca K's do índice.

Então, para k = 2 tem:

{-2, 3}, {3, 4}, {4, 1}, {1, 2}, {2, -1}, a maior soma, por enquanto, é de {3, 4} = 7, índice = 1

 

Então, para k = 3 tem:

{-2, 3, 4}, {3, 4, 1}, {4, 1, 2}, {1, 2, -1}, a maior soma, por enquanto, é de {3, 4, 1} = 8, índice = 1

 

Então, para k = 4 tem:

{-2, 3, 4, 1}, {3, 4, 1, 2}, {4, 1, 2, -1}, a maior soma, por enquanto, é de {3, 4, 1, 2} = 10, índice =1

 

Então, para k = 5 tem:

{-2, 3, 4, 1, 2}, {3, 4, 1, 2, -1}, a maior soma, por enquanto, é de {3, 4, 1, 2} = 10, índice = 1

 

Então, para k = 6 tem:

{-2, 3, 4, 1, 2, -1}, a maior soma de {3, 4, 1, 2} = 10

 

K chegou ao máximo.

 

Logo, determinou-se que o maior é, desde k = 4, índice = 1, o valor 10.

Correto @JorgeGus @nagatonie ?

[] — É programar o incremento de k, a "somatório", comparação e guarda k e o índice que começa [subarray] com maior valor.

 

[arfneto]

Em 06/01/2022 às 11:24, nagatonie disse:

Estou estudando o algoritmo de kadane em c, mas não consigo resolver um porém. Criei um código onde ele lê o valor de soma máxima e mínima, mas o objetivo é adicionar uma subsequência de k elementos de L, com maior e menor somatórios do vetor. 

por exemplo:

L = { -2, 3, 4 , 1, 2, -1}

K = 2

maior somatorio: { 4, 1} = 5

menor somatorio = { -2, 3} = 1 (primeira) | {2, -1} = 1 (ultima)

A minha única dúvida é ler a subsequência do K, pois o código que fiz pega o maior somatório e o menor somatório de todo o L. 

 

O algoritmo de Kadane é uma implementação de uma solução para o problema de determinação de um sub-array contínuo de soma máxima em um array de comprimento L. 

 

Nesse caso o valor de K não é parâmetro e o algoritmo é, bem , o algoritmo de kadane. Em qualquer linguagem. Não se digita o valor de K ou não seria mais o tal algoritmo de Kadane já que a contribuição dele, Kadane, foi justamente no sentido de identificar a sequência em tempo linear.

 

Não entendi.

 

Em 12/01/2022 às 20:13, JorgeGus disse:

Você vai ter que percorrer o vetor 2 vezes, primeiro para encontrar a maior e menor soma, e depois para exibir as sequências que formam k.

 

O algoritmo tratava apenas da soma máxima, e a contribuição de Kadane foi um algortimo que faz isso varrendo o vetor uma única vez, para identificar a soma sem considerar o comprimento, ao menos como se lê em geral. Pode ser adaptado para identificar também a menor soma, e se for preciso também listar os termos se pode criar uma estrutura de apoio para ir salvando a soma local e a soma global com mais os outros 2 valores, o início e o comprimento da sequência...

 

typedef struct 
{
    long int ix; // indice do inicio
    long int K; // comprimento
    long int soma; // pois e'

}   Soma;

Soma menor, maior;