© Jirsak/Shutterstock.com
Ao lidar com conjuntos de dados, eles provavelmente estarão na forma de uma matriz. E essas matrizes geralmente são contíguas. Isso significa que não há “quebras” entre os valores dos dados – eles são armazenados em um único bloco de memória. Esse tipo de array é o centro das atenções quando se trata do problema clássico do Maximum Subarray. Embora existam algumas maneiras de abordar esse problema, uma das melhores maneiras de lidar com isso é usando o algoritmo de Kadane. Se você está se perguntando como usar esse algoritmo e como ele se encaixa na esfera da programação dinâmica, você está no lugar certo. Venha conosco enquanto exploramos o algoritmo de Kadane e como ele é usado para resolver o problema do subarray máximo.
O que é o problema do subarray máximo?
O problema do subarray máximo também é conhecido como o máximo Problema de Subarray Contíguo. Em termos simples, a tarefa que este problema apresenta é encontrar o máximo subarray contíguo dentro de um array, arr[], de tamanho N. Ou seja, encontrar a soma máxima possível de adicionar inteiros no array sem quebras entre eles. Por exemplo, se pegarmos um array [4,-1, 2, 1], a soma máxima seria simplesmente a soma de todos os números inteiros, ou 6.
Para pequenos conjuntos de dados, esta pode ser uma tarefa relativamente simples, e pode ser resolvido facilmente usando o que é conhecido como “abordagem de força bruta”. Isso basicamente significa usar os cálculos mais simples em detrimento da eficiência geral. Desta forma, podemos partir do 0º índice e calcular a soma de todos os subarrays possíveis, começando pelo elemento A[0]. Podemos calcular essas somas de subarray começando com A[1] e continuando até A[n-1], onde n é o tamanho do array. Se chamarmos a soma máxima de um subarray de local_maximum no índice i, podemos calcular tudo isso e então terminar encontrando o máximo dos locais_maximums. Isso nos dará a maior soma possível, que pode ser descrita como o global_maximum.
Como você pode esperar, isso pode funcionar razoavelmente bem para arrays muito pequenos, mas é bastante ineficiente para conjuntos de dados maiores. A complexidade de tempo é quadrática, ou O(n2), o que significa que a complexidade aumenta rapidamente com o aumento do tamanho da entrada. Portanto, vamos precisar de um processo mais eficiente e elegante. É aqui que entra a programação dinâmica.
Como a programação dinâmica pode ajudar?
A programação dinâmica é uma abordagem para resolver problemas complicados reduzindo-os a uma coleção de problemas mais simples. Esses problemas mais fáceis são resolvidos e suas soluções são armazenadas em uma estrutura de dados, como um array. Essas soluções podem ser acessadas quando estamos resolvendo o mesmo tipo de problema, evitando a necessidade de resolvê-los novamente e acelerando os cálculos gerais.
Seria muito benéfico se pudéssemos aplicar os princípios de programação dinâmica para o nosso problema de subarray máximo. Felizmente, podemos, e é exatamente isso que o algoritmo de Kadane se propõe a fazer. Então, vamos entrar nisso.
A programação dinâmica é uma abordagem para resolver problemas complicados, reduzindo-os a uma coleção de problemas mais simples.
©hafakot/Shutterstock.com
Algoritmo de Kadane
Como mencionado brevemente, o algoritmo de Kadane usa programação dinâmica para computar uma solução eficiente para o Problema do Subarranjo Máximo. O algoritmo funciona armazenando a soma máxima do subarray contíguo no índice atual. Isso é então comparado com a soma máxima encontrada até agora. Se for maior que a soma máxima encontrada até o momento, ela é atualizada com o novo valor.
Uma grande vantagem do algoritmo de Kadane é sua velocidade, mostrada em sua complexidade de tempo de O(n). Isso significa que a complexidade de tempo aumenta linearmente com o aumento do tamanho da entrada, o que é muito melhor do que a complexidade de tempo quadrática da abordagem de força bruta. A complexidade do espaço também é boa, pois o algoritmo é estável – isso significa que uma quantidade constante de memória é necessária durante o processo, pois apenas duas variáveis precisam ser armazenadas (são o global_maximum e o local_maximum).
Algoritmo de Kadane em ação
Vamos pegar o array [4,-1, 2, 1] novamente. Se invertermos a abordagem de força bruta e começarmos com o elemento A[n] (neste caso, 1), podemos calcular a soma de todos os subarranjos possíveis e continuar com A[n-1], A[n-2] até que tenhamos concluído todos eles.
Observando os dois últimos elementos, A[3] e A[4], podemos ver que o local_maximum é 5 e 6, respectivamente. Mas, se soubermos local_maximum[3], não precisamos calcular todas as somas de subarray para A[4]. Isso ocorre porque já conhecemos os resultados de A[3] e o local_maximum[3]. Precisamos apenas verificar dois subarrays, aquele contendo A[4] sozinho e a soma de A[4] e local_maximum[3]. Neste caso, seria A[4} + local_maximum[3], que é 6. Esta é a mesma resposta que obtemos se calcularmos todas as somas de subarray para A[4].
Este princípio é o que sustenta o algoritmo de Kadane e pode ser descrito da seguinte forma:
local_maximum[i]=max(A[i], A[i] + local_maximum[i-1])
Ou, em outras palavras, o local_maximum no índice i é o máximo de A[i] e a soma de A[i] e local_maximum no índice i-1.
Portanto, só precisamos encontrar o máximo de A[i] e A[i] + local_maximum[i-1] para encontrar o máximo em cada índice i. Portanto, precisamos apenas encontrar cada local_maximum para encontrar o subarray máximo. Esta é uma maneira muito mais eficiente de lidar com o problema do subarray máximo.
O funcionamento do algoritmo de Kadane
Vamos percorrer as etapas que o algoritmo de Kadane usa para calcular o subarray máximo.
p> O algoritmo exigirá apenas um loop, iterando de i[0[ a i[n-1].O local_maximum[i] será calculado para cada elemento, que depende de local_maximum[i-1].O local_maxium é comparado para o global_maximum. Se for maior, global_maximum será atualizado. Isso é repetido para cada índice até que a maior soma de um subarray contíguo seja encontrada.
Implementação do algoritmo de Kadane
Para mostrar como o algoritmo de Kadane pode ser implementado, vamos usar Python no ambiente Spyder. Vamos dar uma olhada em como o código funciona na prática.
from sys import maxsize def solveMaxSubArrayProblem(input): n=len(input) globalMaxSum=-maxsize-1 localMaxSum=0 for i in range(0, n): localMaxSum=max(input[i], input[i] + localMaxSum) if(localMaxSum>globalMaxSum): globalMaxSum=localMaxSum return globalMaxSum if_name_==”_main_”input=[1,-2, 5,-3, 4,-1, 6] resultado=solveMaxSubArrayProblem(input) print(result) 11
Em primeiro lugar, o recuo adequado em Python é a chave para executar o código corretamente. Para começar, estamos importando a função “maxsize”, que é usada para encontrar o valor máximo.
Em seguida, estamos definindo “solveMaxSubArrayProblem” como uma função do array “input” de comprimento n , com globalMaxSum inicializado como o valor inteiro mínimo. Isso é feito para garantir que qualquer soma de subarray calculada seja maior que esse valor.
O local_maximum irá variar e é definido inicialmente como 0.
“for” refere-se a um loop, que é usado para percorrer cada elemento da matriz.
Para cada iteração,”localMaxSum”é atualizado para o localMaxSum do elemento atual ou o elemento mais o localMaxSum anterior.
Se localMaxSum é maior que o globalMaxSum atual, o último é atualizado para refletir essa alteração.
Depois que o processo iterativo é concluído, globalMaxSum é igual ao subarray contíguo máximo e esse resultado é retornado.
Por último, “if __name__==“”__main__”” testa a função criando o array que segue e usando a função definida nele, e então imprime o resultado.
Para o array [1 ,-2, 5,-3, 4,-1, 6], o subarray contíguo máximo tem uma soma de 11.
©”TNGD.com
Conclusão
Cobrimos o princípio por trás da programação dinâmica. Também mostramos como o algoritmo de Kadane usa isso para resolver o Problema do Subarranjo Máximo. As vantagens disso foram descritas. O algoritmo de Kadane é relativamente simples de entender e usar, com complexidade eficiente de tempo e espaço. Quando se trata de resolver o problema do subarray máximo, o algoritmo de Kadane é uma das maneiras mais rápidas de fazer isso.
A seguir…
Algoritmo de Kadane: uma abordagem eficiente para o problema do subarray máximo , Explicado com fotos Perguntas frequentes (perguntas frequentes)
O que é um subarray?
Um subarray é parte de um array ininterrupto, ou seja, sem quebras entre números inteiros. Isso é descrito como contíguo. Um subarray pode consistir em um elemento. Eles são usados principalmente ao trabalhar com conjuntos de dados, para fazer coisas como encontrar o subarray contíguo máximo.
O que é programação dinâmica?
Programação dinâmica refere-se a uma técnica para resolver problemas complexos, dividindo-os em outros mais simples. Cada subsolução só precisa ser calculada uma vez e é armazenada em um cache temporário. Assim, cálculos redundantes são evitados e os processos são significativamente acelerados. A programação dinâmica é freqüentemente usada para otimizar soluções e projetar algoritmos, como o algoritmo de Bellman-Ford para encontrar o caminho mais curto em um grafo. Normalmente, os subproblemas são resolvidos de baixo para cima, o que significa que os problemas mais simples são resolvidos primeiro. Essas soluções são então combinadas para resolver o problema inicial.
Qual é o problema do subarranjo máximo?
Este é um problema clássico de programação que envolve encontrar a maior soma subarray contíguo dentro de um array de inteiros. A solução para este problema tem muitas aplicações, em áreas como finanças, análise de dados e processamento de sinais. O algoritmo mais eficiente para resolver isso é o algoritmo de Kadane.
O que é o algoritmo de Kadane?
O algoritmo de Kadane é uma abordagem eficiente para resolver o problema de máximo subarranjo contíguo. O algoritmo funciona calculando o local_maximum e o global_maximum. Ao iterar sobre o array começando da esquerda, essas variáveis são atualizadas a cada passo, com o local_maximum máximo até agora substituindo o global_maximum se seu valor for maior. Depois que todos os locais_maximums tiverem sido calculados, o máximo subarray contíguo será conhecido e igual ao global_maximum.
Qual é a abordagem de força bruta para resolver o problema do Maximum Subarray?
A abordagem de força bruta envolve iterar sobre todos os subarrays possíveis em um array e calcular as somas dos subarrays. O máximo subarray contíguo pode então ser encontrado, mas o processo não é muito eficiente, pois cada subarray deve ser calculado.
Quais são as desvantagens de usar o algoritmo de Kadane?
Embora o algoritmo de Kadane seja simples e eficiente, ele só pode ser realmente usado para resolver o problema do subarranjo máximo. A saída que produz também é limitada, pois contém apenas a soma do subarray máximo. Nenhuma informação é fornecida sobre o próprio array, o que pode ser necessário para algumas aplicações. Por fim, embora o algoritmo seja rápido, a solução não é ótima em todos os casos.
Qual é a complexidade de tempo do algoritmo de Kadane?
A complexidade de tempo de O algoritmo de Kadane é O(n).
O algoritmo de Kadane pode ser usado com arrays não contíguos?
Não, o algoritmo não pode ser usado com arrays não contíguos.
Como o algoritmo de Kadane pode ser modificado para encontrar o subarray com a soma mínima?
Podemos simplesmente substituir a função maxsize por minsize , e inicializar as variáveis para infinito em vez de zero.
O algoritmo de Kadane pode ser usado com uma matriz com todos os inteiros negativos?
Sim, o algoritmo irá retorne o subarray com a menor soma negativa neste caso.