Algoritmo de Kadence: Subarranjo Contíguo de Maior Soma
Sarah Chen
Qual é a maior submatriz contígua de soma?
Um subarray é uma parte contínua de um array. Pode ser um único elemento de uma matriz ou alguma fração da matriz. A submatriz contígua de maior soma significa uma submatriz que possui o valor de soma máximo.
Por exemplo, uma matriz é {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Suas submatrizes podem ser: {-10,5,1,6} ou {5,1,6} ou {2,7,3, -5} etc. Mas {5,1,6,3} não pode ser uma subarray porque eles não estão mantendo as sequências.
Se você notar, entre todos os subarranjos, o seguinte subarranjo destacado (5,1,6) tem o valor máximo de soma:
A soma do subarray {5,1,6} = 11, é a soma máxima em todas as combinações possíveis de subarray do array acima. Portanto, para a matriz acima, a submatriz máxima é {5,1,6}.
Algoritmo de Kadence: Subarranjo Contíguo de Maior Soma
Abordagem simples para resolver o subarranjo contíguo de maior soma
A maneira simples de resolver esse problema é usar dois loops para encontrar todas as submatrizes, calcular a soma e então encontrar seu valor máximo.
Aqui está o fluxograma para a abordagem simples para encontrar a submatriz contígua de maior soma. Esta é uma abordagem de força bruta, pois examinamos todos os subarranjos possíveis.
Aqui estão as etapas simples para fazer isso.
Passo 1) Inicialize max_sum com valor inteiro mínimo e atribua as variáveis “begin” e “end” com zero.
Passo 2) Sejam i e j o índice do array, onde “j” é maior que igual a “i”. Ele representa o índice inicial da submatriz e “j” representa o índice final da submatriz.
Passo 3) “Current_sum” conterá a soma do subarray. Após calcular a soma atual, verifique se current_sum é maior que max_sum.
Passo 4) Se current_sum for maior, substitua max_sum pela soma atual.
Passo 5) Verifique se “j” chega ao final do array ou não. Se “j” atingir o final do array, aumente “i” e altere o valor current_sum para 0.
Passo 6) Execute todas essas etapas, até que “i” chegue ao final do array.
Passo 7) No final desses dois loops, o max_sum conterá a maior soma do subarray.
Pseudocódigo para abordagem simples
function maximumSubarraySum():
input: array
for all possible subArray from array:
calculate sum of each sub array
store the maximum subArray
return the maximum sum
C++ Implementação de abordagem simples
#include <stdio.h>
#include <iostream>
using namespace std;
void maximumSubarraySum(int array[], int n) {
int max_sum = -1e9;
int begin = 0;
int end = 0;
for (int i = 0; i < n; i++) {
int current_sum = 0;
for (int j = i; j < n; j++) {
current_sum += array[j];
if (max_sum < current_sum) {
max_sum = current_sum;
begin = i;
end = j;
}
}
}
cout << "largest sum is " << max_sum << endl;
cout << "largest sum contiguous subarray: ";
for (int i = begin; i <= end; i++) {
cout << array[i] << "\t";
}
}
int main() {
int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
maximumSubarraySum(array, sizeof(array) / sizeof(array[0]));
}
Saída:
largest sum is 12 largest sum contiguous subarray: 5 1 6
Python Implementação de abordagem simples
def maximumSubarraySum(numbers):
max_sum,begin,end = -1e9, 0 , 0
for i in range(len(numbers)):
current_sum=0
for j in range(i,len(numbers)):
current_sum+=numbers[j]
if max_sum<current_sum:
max_sum=current_sum
begin,end=i,j
print("largest sum is ",max_sum)
print("largest sum contiguous subarray: ",end="")
for i in range(begin,end+1):
print(numbers[i],end='\t')
numbers = [-10,5,1,6,-9,2,-7,3,-5]
maximumSubarraySum(numbers)
Saída:
largest sum is 12 largest sum contiguous subarray: 5 1 6
Algoritmo de Kadane para encontrar o subarranjo contíguo de maior soma
O Algoritmo de Kadane é uma espécie de método de “Programação Dinâmica”. Aqui usaremos um loop em vez de dois loops. A implementação geral do Algoritmo de Kadane funciona apenas para matrizes de números positivos.
Precisamos apenas de duas variáveis para encontrar o subarranjo contíguo de maior soma. Aqui está o fluxograma do Algoritmo de Kadane:
Aqui estão as etapas para o Algoritmo de Kadane:
Passo 1) Crie duas variáveis, current_sum e max_sum.
“Current_sum” manterá o valor da soma máxima que termina em um índice de array específico, enquanto “max_sum” armazenará o valor máximo da soma até o momento.
Passo 2) Adicionaremos o valor com current_sum para cada elemento do array. Então verificaremos duas condições abaixo:
- Se current_sum for menor que o elemento atual, então o valor current_sum será o elemento atual.
- Se max_sum for menor que current_sum, então max_sum será current_sum.
Passo 3) Realizando a etapa anterior para todo o array, teremos o subarray contíguo de maior soma na variável “max_sum”.
Exemplo de Algoritmo de Kadane
Demonstraremos o algoritmo de Kadanes com um array de tamanho pequeno e discutiremos cada etapa para encontrar o subarray contíguo de maior soma.
Vamos supor que o array fornecido seja semelhante ao seguinte:
Aqui estão as etapas do Algoritmo de Kadane:
Passo 1) Crie duas variáveis, current_sum e max_sum. Atribua INT_MIN ao max_sum e zero ao current_sum. (Aqui, INT_MIN significa o número inteiro mínimo).
Passo 2) No índice 0, o valor é 4. Portanto, current_sum = 0 + 4 ou 4. Aqui current_sum é maior que max_sum, max_sum será 4.
Passo 3) No índice 1, o valor é -2. Portanto, soma_atual = 4 + (-2) ou 2.
Desta vez, current_sum é menor que max_sum. Como resultado, o valor de max_sum não será atualizado.
Passo 4) O próximo valor é 1. Se somarmos isso com a soma_atual, então a soma_atual será 3. Ainda assim, a soma_max é maior que a soma_atual. Portanto, max_sum não será atualizado.
Passo 5) No índice 3, o valor é três. Atualizaremos o valor incrementando a soma_atual em 3. Portanto, a soma_atual será 6.
Neste caso, max_sum é menor que current_sum. Portanto, max_sum será atualizado com o valor de current_sum.
Passo 6) Para o último elemento do array, temos -1. Se adicionarmos isso à soma_atual, a soma_atual será 5, que é menor que a soma_max. Portanto, max_sum permanecerá 6.
Quando chegamos ao final do array, o algoritmo termina aqui. Agora, “max_sum” contém o subarray de soma máxima. Qual é 5. A submatriz é {4,-2,1,3}.
Pseudocódigo para o algoritmo de Kadane
function KadaneAlgorithm():
input: array
maximum_sum, current_sum = 0
for each elements in array:
add the element with current_sum
if current_sum is greater than the maximum_sum
then maximum_sum = current_sum
if current_sum is less than the element
then current_sum = element
return the value of maximum_sum
C++Implementação do Algoritmo de Kadane
#include < iostream >
using namespace std;
void kadane(int array[], int n) {
int current_sum = 0;
int max_sum = -1e9;
// -1e9 means -10000000
for (int i = 0; i < n; i++) {
current_sum += array[i];
if (max_sum < current_sum) {
max_sum = current_sum;
}
if (current_sum < array[i]) {
current_sum = array[i];
}
}
cout << "largest sum is " << max_sum << endl;
}
int main() {
int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
kadane(array, sizeof(array) / sizeof(array[0]));
}
Saída:
largest sum is 12
Python Implementação do Algoritmo de Kadane
def kadane(numbers):
current_sum = 0
max_sum = -1e9
for i in range(len(numbers)):
current_sum += numbers[i]
if max_sum < current_sum:
max_sum = current_sum
if current_sum<numbers[i]:
current_sum = numbers[i]
print("largest sum is ",max_sum)
kadane([-10,5,1,6,-9,2,-7,3,-5])
Saída:
largest sum is 12
Análise de complexidade para a maior submatriz contígua de soma
A abordagem simples usa dois loops. Esse método calcula todas as somas possíveis de submatrizes para encontrar a maior delas. É uma abordagem de força bruta. Cada loop é executado até o final do ordem.
Se uma matriz tiver um total de N elementos, então usando dois loops, passaremos por N2 elementos. Como resultado, a complexidade de tempo para uma abordagem simples para encontrar a maior soma de submatrizes contíguas será O(N2). Aqui, “O” significa a função de complexidade.
Por outro lado, o Algoritmo de Kadane é o método de Programação Dinâmica para encontrar a submatriz de soma contígua máxima. Se você seguir o exemplo ou o código, verá que estamos usando apenas um loop.
Como resultado, se a matriz de entrada tiver um tamanho de N, então a complexidade de tempo do algoritmo de Kadane será O(N). Isso é mais rápido do que a abordagem simples. Por exemplo, uma matriz contendo 100 elementos. A abordagem simples levará 100*100 ou 10,000 tempo de CPU. Mas o Algoritmo de Kadane levará apenas 100 CPUs.
