Published

25/05/2026

Modified

22/04/2026

Soma Máxima em um Intervalo (Algoritmo de Kadane)

A Intuição do Acumulativo

Dada uma sequência qualquer de números positivos e negativos \(S=(s_1,s_2,s_3,...,s_n)\), qual a maior soma que podemos obter escolhendo um “pedaço” ininterrupto desta fita (subconjunto de termos adjacentes)?

Se a sequência for, por exemplo, \((1, -3, 5, -2, 1, -1)\). Não podemos pular números. A soma máxima contínua desse bloco é \(4\), pegando os termos \((5, -2, 1)\).

Embora exista uma versão baseada em Paradigmas Gulosos / Divisão e Conquista, por trás há uma ideia magistral e simples de Programação Dinâmica batizada de Algoritmo de Kadane:

Se \(v_i\) é a maior soma possível que conseguimos arrastar até terminar exatamente no índice \(i\), então para o próximo elemento \(i+1\) temos duas opções: 1. “Estender a fita”: O número em \(i+1\) é agregado ao lucro/prejuízo somado que arrastamos de trás (\(s_{i+1} + v_i\)). 2. “Queimar o passado”: A herança de trás é tão horrivelmente negativa que o próprio número isolado \(s_{i+1}\) é melhor sozinho recomeçando a fita dali. Daí vem nossa equação de transição: \(v_{i+1} = \max(s_{i+1}, s_{i+1} + v_i)\)

O Algoritmo \(\mathcal{O}(N)\)

Como só precisamos rastrear o “Acumulado Atual” e o “Melhor Histórico Gravado”, nossa “Tabela DP” pode ser esmagada em 2 variáveis globais sem arrays!

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

int algoritmo_de_kadane(const vector<int>& s) {
    if (s.empty()) return 0;
    
    int somaLocal = s[0];
    int somaGlobalMax = s[0];
    
    // Varredura Linear
    for(size_t i = 1; i < s.size(); i++) {
        // Decide se prolonga a faixa, ou reseta a fita partindo daqui
        somaLocal = max(s[i], somaLocal + s[i]);
        
        // Mantém gravado no Guinness Book a maior marca já atingida nesa rodada
        somaGlobalMax = max(somaGlobalMax, somaLocal);
    }
    
    return somaGlobalMax;
}

void executando_testes() {
    // Cenário Metáfora
    vector<int> fita = {1, -3, 5, -2, 1, -1};
    
    // O corte de 5 + (-2) + 1 deve lucrar 4. 
    assert(algoritmo_de_kadane(fita) == 4);
    
    // E se tudo for negativo? O Máximo é o menos amaldiçoado!
    vector<int> malAmaldicoada = {-10, -5, -8, -20};
    assert(algoritmo_de_kadane(malAmaldicoada) == -5);

    cout << "[✅] Testes do Algoritmo de Kadane finalizados! Fita ininterrupta máxima encontrada.\n";
}

int main() {
    executando_testes();
    return 0;
}

O Kadane é essencial em Visão Computacional de 2D (ex: Achar o retângulo de soma máxima cortando submatrizes e projetando em 1D) e estatísticas de Mercado Financeiro (máximo lucro temporal ininterrupto).

Exercício Prático

  • Procure as abordagens em 2D de Kadane para “Maximum Sum Subrectangle”. (Problema clássico URI 108). Você ficará fascinado ao ver um algoritmo complexo 2D esmagado usando colunas tratadas como blocos 1D iteráveis.
Back to top