Algoritmo de Kadence: Subarranjo Contíguo de Maior Soma

Qual é a maior soma de submatriz contígua?

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, considere o array {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Seus subarrays podem ser {-10, 5, 1, 6}, {5, 1, 6} ou {2, -7, 3, -5}, e assim por diante. No entanto, {5, 1, 6, 3} não pode ser um subarray porque os elementos não estão em uma sequência contígua.

Se você observar, dentre todos os subconjuntos de matrizes, o subconjunto destacado {5, 1, 6} possui o maior valor de somatório:

A soma do subconjunto {5, 1, 6} é 12, a soma máxima entre todos os subconjuntos possíveis do array acima. Portanto, para este array, o subconjunto contíguo com a soma máxima é {5, 1, 6}.

Abordagem simples para resolver o problema da maior soma de submatriz contígua.

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 da abordagem simples para encontrar a maior soma de subvetores contíguos. Esta é uma abordagem de força bruta, pois percorremos todos os subvetores possíveis.

Aqui estão as etapas simples para fazer isso.

Passo 1) Inicializar soma_máxima com o menor valor inteiro e definido começar e final para zero.

Passo 2) Deixei i e j sejam índices de matriz onde j é maior que ou igual a i; i marca o início do subconjunto e j seu fim.

Passo 3) soma_atual contém a soma acumulada. Após cada atualização, verifique se soma_atual é melhor que soma_máxima.

Passo 4) If soma_atual é maior, substitua soma_máxima com ela.

Passo 5) Ao j Ao atingir o final da matriz, incremente. i e resetar soma_atual para 0.

Passo 6) Repetir até i alcança o final da matriz. soma_máxima então contém a soma do maior subconjunto.

Apelido Code para uma abordagem simples

function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        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 a maior soma de submatriz contígua.

O Algoritmo de Kadane é um método de Programação Dinâmica que utiliza um único laço em vez de dois. Ele lida com arrays contendo números positivos e negativos, desde que pelo menos um valor seja não negativo.

Precisamos apenas de duas variáveis ​​para encontrar a maior soma de submatriz contígua. Aqui está o fluxograma:

Aqui estão as etapas para o Algoritmo de Kadane:

Passo 1) Crie duas variáveis, soma_atual e soma_máxima.

soma_atual Mantém a soma máxima que termina em um índice específico da matriz, enquanto soma_máxima Armazena o maior valor de soma observado até o momento.

Passo 2) Adicione cada elemento da matriz a soma_atualEm seguida, verifique as duas condições abaixo:

• If soma_atual se for menor que o elemento atual, então soma_atual torna-se o elemento atual.
• If soma_máxima é inferior a soma_atual, Em seguida soma_máxima torna-se soma_atual.

Passo 3) Após repetir a etapa anterior para toda a matriz, soma_máxima detém a maior soma de submatriz contígua.

Exemplo de Algoritmo de Kadane

Demonstramos o Algoritmo de Kadane em um pequeno arranjo e descrevemos cada passo para encontrar o subarranjo contíguo de maior soma.

Vamos supor que o array fornecido seja semelhante ao seguinte:

Aqui estão os passos do Algoritmo de Kadane:

Passo 1) Crie duas variáveis, soma_atual e soma_máximaAtribua INT_MIN a soma_máxima e zero a soma_atualAqui, INT_MIN representa o menor valor inteiro.

Passo 2) No índice 0, o valor é 4. Portanto, soma_atual = 0 + 4 = 4. Já que soma_atual é maior que soma_máxima, soma_máxima torna-se 4.

Passo 3) No índice 1, o valor é -2. Portanto, soma_atual = 4 + (-2) = 2.

Desta vez soma_atual é inferior a soma_máximaConsequentemente, o valor de soma_máxima não é atualizado.

Passo 4) O próximo valor é 1. Adicionando-o a soma_atual dá 3. Já que soma_máxima (4) ainda é maior que soma_atual, soma_máxima não é atualizado.

Passo 5) No índice 3, o valor é 3. Incrementando soma_atual por 3 dá soma_atual = 6.

Neste caso, soma_máxima É menor que soma_atual, assim soma_máxima é atualizado com o valor de soma_atual.

Passo 6) Para o último elemento da matriz, temos -1. Adicionando-o a soma_atual resulta em 5, que é menor que soma_máxima. Assim, soma_máxima permanece 6.

Ao chegarmos ao final do array, o algoritmo termina aqui. Agora, soma_máxima contém a soma máxima, que é 6. O subconjunto é {4, -2, 1, 3}.

Apelido Code para o algoritmo de Kadane

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each element 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 -1,000,000,000
    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 utiliza dois loops para calcular a soma de todos os subconjuntos possíveis e localizar o maior deles. É uma abordagem de força bruta; cada loop percorre todo o intervalo até o final da matriz. ordemdando O(N²) tempo.

O algoritmo de Kadane usa apenas um laço, resultando em tempo O(N) e espaço extra O(1). Em um array de 100 elementos, a abordagem simples realiza 100 × 100 = 10,000 operações, enquanto a de Kadane realiza apenas 100 — uma aceleração drástica para entradas grandes.

Perguntas Frequentes