Subarray de Soma Máxima com Algoritmo de Kadane (Kadane’s Algorithm)

Definição

O Algoritmo de Kadane é uma solução eficiente para encontrar o subarray contíguo de soma máxima em um array de números inteiros (positivos, negativos ou mistos).

Em vez de testar todas as combinações possíveis (o que seria lento), ele percorre o array apenas uma vez, mantendo a soma máxima até o momento e a soma atual.

Por que usar

• Resolve o problema de forma eficiente em tempo linear O(n);
• Usa uma ideia simples de programação dinâmica: a solução ótima em um ponto depende apenas da solução anterior;
• É amplamente utilizado em problemas de análise de séries, desempenho financeiro, detecção de padrões, entre outros.

Exemplo prático (Python)

def max_subarray_kadane(nums):
    max_atual = max_global = nums[0]

    for num in nums[1:]:
        max_atual = max(num, max_atual + num)
        if max_atual > max_global:
            max_global = max_atual

    return max_global

# Exemplo
lista = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_kadane(lista))  # Saída: 6

Visualização passo a passo

Array inicial: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

| Posição | Elemento | max_atual              | max_global |
| ------- | -------- | ---------------------- | ---------- |
| 0       | -2       | -2                     | -2         |
| 1       | 1        | max(1, -2 + 1) = 1     | 1          |
| 2       | -3       | max(-3, 1 + (-3)) = -2 | 1          |
| 3       | 4        | max(4, -2 + 4) = 4     | 4          |
| 4       | -1       | max(-1, 4 + (-1)) = 3  | 4          |
| 5       | 2        | max(2, 3 + 2) = 5      | 5          |
| 6       | 1        | max(1, 5 + 1) = 6      | 6          |
| 7       | -5       | max(-5, 6 + (-5)) = 1  | 6          |
| 8       | 4        | max(4, 1 + 4) = 5      | 6          |

Em cada linha:

• max_atual considera o maior entre:
  (a) o número atual, e
  (b) a soma do número atual com o max_atual anterior.
• max_global guarda o maior max_atual encontrado até o momento.

Maior soma encontrada: 6 (subarray [4, -1, 2, 1])

Saída

6

Relacionados

• Programação Dinâmica
• Memoization
• Dividir para Conquistar