Aula por Arthur Lobo
Nessa aula, vamos falar sobre técnicas usadas para encontrar a maior soma de um intervalo contínuo em um vetor e suas aplicações.
Motivação inicial
Vamos imaginar o seguinte problema: Dado um vetor inicial de tamanho $$N$$, $$A_1, A_2 … A_N$$, com números inteiros entre $$-100$$ e $$100$$, responda qual é a maior soma de um intervalo contínuo. Formalmente, diga qual o maior valor de $$A_i+A_{i+1}+…+A_j$$, com $$1 \le i \le j \le N$$.
Se quiser ler o enunciado inteiro e com mais detalhes, clique aqui.
Uma primeira ideia que podemos ter para resolver o problema é testar todos os intervalos $$(i,j)$$ (começando em $$i$$ e terminando em $$j$$) e ver qual deles tem a maior soma. Para isso podemos criar uma função $$soma(i,j)$$, que retorna a soma de $$i$$ até $$j$$ fazendo um $$for$$ no intervalo inteiro e somando os valores correspondentes Essa solução tem a complexidade $$O(N^3)$$, pois testamos $$O(N^2)$$ pares e a função $$soma(i,j)$$ funciona em $$O(N)$$.
Ainda podemos melhorar essa solução usando soma de prefixo: primeiro calculamos o vetor de somas de prefixo $$S$$, em que $$S_i$$ guardará a soma $$A_1+A_2+…+A_i$$, e então podemos fazer com que a função $$soma(i,j)$$ seja respondida em $$O(1)$$, já que podemos apenas retornar $$S_j – S_{i-1}$$. Dessa maneira, podemos fazer essa ideia rodar em $$O(N^2)$$, mas ainda podemos fazer melhor!
Algoritmo de Kadane
A ideia do algoritmo de Kadane é realizarmos uma solução gulosa. Vamos iterar do $$1$$ até o $$N$$, quando estivermos em $$i$$, sempre manteremos 2 valores: a resposta máxima até aqui e o valor do intervalo de soma máximo terminando em $$i$$, guardaremos eles em $$resp$$ e $$soma$$, respectivamente.
O algoritmo é o seguinte, digamos que acabamos de calcular a iteração de $$i-1$$, na iteração de $$i$$ vamos seguir os seguintes passos:
- Primeiro, verificamos se $$soma$$ é menor que $$0$$, caso seja, fazemos com que ela retorne a ser $$0$$. A ideia é que sempre que o intervalo ficar negativo, vamos descartar ele inteiro.
- Depois, adicionamos $$A_i$$ em $$soma$$, fazendo $$soma = soma + A_i$$. Nesse momento, é garantido que $$soma$$ guarda o valor do intervalo de soma máxima que termina em $$i$$ (vamos provar isso logo em seguida).
- Por último, iremos atualizar $$resp$$ caso $$soma$$ seja maior que $$resp$$ fazendo $$resp = max(resp,soma)$$
A intuição por trás do algoritmo de Kadane é que sempre que a soma do intervalo fica menor que $$0$$, nós resetamos ela, fazendo com que volte a ser $$0$$. Isso faz com que, sempre que estamos em $$i$$, $$soma$$ guardá o valor do intervalo de soma máxima que termina em $$i$$, portanto, pegamos o intervalo de soma máxima do vetor inteiro. A prova do porque podemos resetar (fazer o início e o final do intervalo ser $$i$$) fica como um exercício para o leitor, mas a ideia é imaginar o que aconteceria se fosse melhor mudar o início do intervalo para uma posição diferente de $$i$$.
Soma de Prefixo
Além da solução com o algoritmo de Kadane, esse problema também pode ser resolvido utilizando somas de prefixo. Além de ser mais intuitiva, a solução com soma de prefixo pode ser usada em diversas variações do problema. Agora vamos olhar ela mais de perto:
No início da aula, falamos sobre fazer um vetor de somas de prefixos $$S$$, em que $$S_i$$ guarda $$A_1+A_2+…+A_i$$ (em particular, $$S_0 = 0$$), e usar isso para descobrir a soma entre quaisquer de $$i$$ até $$j$$ ($$i \le j$$) fazendo a conta $$S_j-S_{i-1}$$. Portanto, queremos encontrar o valor máximo de $$S_j-S_{i-1}$$.
Assim como no algoritmo de Kadane, nosso objetivo vai ser descobrir qual a maior soma de intervalo terminando em cada $$j$$. Para isso, vamos fixar o $$j$$ na nossa conta e olhar apenas para o $$i$$, Fazemos isso para todo $$j$$ de $$1$$ até $$N$$.
Queremos encontrar o maior valor de $$S_j-S_{i-1}$$, a partir do momento que fixamos um $$j$$, o valor do primeiro termo ($$S_j$$) é fixado também, então nosso objetivo virou apenas maximizar o segundo termo, ou seja, $$-S_{i-1}$$, e maximizar isso é o mesmo que minimizar $$S_{i-1}$$, já que está ele subtraindo. Como temos que $$1 \le i \le j \Rightarrow 0 \le i-1 \le j-1$$, então queremos que $$S_{i-1}$$ seja o menor valor entre $$S_0, S_1,…,S_{j-1}$$.
Para computarmos isso em cada $$j$$ de $$1$$ até $$N$$, podemos iterar nessa ordem, guardando sempre o valor do menor prefixo até $$j-1$$ na variável $$menor$$, ao mesmo tempo que vamos atualizando a resposta em cada iteração, guardando ela em $$resp$$:
Começamos com $$menor = 0$$ e $$resp = -infinito$$ (com infinito sendo um número muito grande), e para cada $$j$$ de $$1$$ até $$N$$ nosso algoritmo realizará os seguintes passos:
- Primeiro, vemos se $$S_{j-1} < menor$$, e caso for, o atualizamos fazendo $$menor = min(menor,S_{j-1})$$.
- Agora sabemos que o valor do intervalo de soma máxima que termina em $$j$$ é $$S_j-menor$$, então comparamos a resposta atual com essa possível resposta fazendo $$resp = max(resp,S_j-menor)$$.
A intuição por trás do algoritmo é que sempre queremos subtrair o menor valor possível de $$S_j$$, então a melhor opção é pegar o prefixo com a menor soma até $$j-1$$. Vale ressaltar que o problema inicial diz que temos que pegar pelo menos um valor do vetor, então se todos os elementos em $$A$$ fossem negativos, nossa resposta seria negativa. Mas caso um problema fale que podemos escolher não pegar nenhum valor do vetor, então caso todos os elementos em $$A$$ sejam negativos, a resposta será $$0$$.
Problemas para praticar
Agora é a sua vez! Tente fazer esses problemas que usam os algoritmos ensinados na aula de hoje ou ideias semelhantes: