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 , , com números inteiros entre e , responda qual é a maior soma de um intervalo contínuo. Formalmente, diga qual o maior valor de , com .
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 (começando em e terminando em ) e ver qual deles tem a maior soma. Para isso podemos criar uma função , que retorna a soma de até fazendo um no intervalo inteiro e somando os valores correspondentes Essa solução tem a complexidade , pois testamos pares e a função funciona em .
Ainda podemos melhorar essa solução usando soma de prefixo: primeiro calculamos o vetor de somas de prefixo , em que guardará a soma , e então podemos fazer com que a função seja respondida em , já que podemos apenas retornar . Dessa maneira, podemos fazer essa ideia rodar em , mas ainda podemos fazer melhor!
Algoritmo de Kadane
A ideia do algoritmo de Kadane é realizarmos uma solução gulosa. Vamos iterar do até o , quando estivermos em , sempre manteremos 2 valores: a resposta máxima até aqui e o valor do intervalo de soma máximo terminando em , guardaremos eles em e , respectivamente.
O algoritmo é o seguinte, digamos que acabamos de calcular a iteração de , na iteração de vamos seguir os seguintes passos:
- Primeiro, verificamos se é menor que , caso seja, fazemos com que ela retorne a ser . A ideia é que sempre que o intervalo ficar negativo, vamos descartar ele inteiro.
- Depois, adicionamos em , fazendo . Nesse momento, é garantido que guarda o valor do intervalo de soma máxima que termina em (vamos provar isso logo em seguida).
- Por último, iremos atualizar caso seja maior que fazendo
A intuição por trás do algoritmo de Kadane é que sempre que a soma do intervalo fica menor que , nós resetamos ela, fazendo com que volte a ser . Isso faz com que, sempre que estamos em , guardá o valor do intervalo de soma máxima que termina em , 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 ) 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 .
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 , em que guarda (em particular, ), e usar isso para descobrir a soma entre quaisquer de até () fazendo a conta . Portanto, queremos encontrar o valor máximo de .
Assim como no algoritmo de Kadane, nosso objetivo vai ser descobrir qual a maior soma de intervalo terminando em cada . Para isso, vamos fixar o na nossa conta e olhar apenas para o , Fazemos isso para todo de até .
Queremos encontrar o maior valor de , a partir do momento que fixamos um , o valor do primeiro termo () é fixado também, então nosso objetivo virou apenas maximizar o segundo termo, ou seja, , e maximizar isso é o mesmo que minimizar , já que está ele subtraindo. Como temos que , então queremos que seja o menor valor entre .
Para computarmos isso em cada de até , podemos iterar nessa ordem, guardando sempre o valor do menor prefixo até na variável , ao mesmo tempo que vamos atualizando a resposta em cada iteração, guardando ela em :
Começamos com e (com infinito sendo um número muito grande), e para cada de até nosso algoritmo realizará os seguintes passos:
- Primeiro, vemos se , e caso for, o atualizamos fazendo .
- Agora sabemos que o valor do intervalo de soma máxima que termina em é , então comparamos a resposta atual com essa possível resposta fazendo .
A intuição por trás do algoritmo é que sempre queremos subtrair o menor valor possível de , então a melhor opção é pegar o prefixo com a menor soma até . Vale ressaltar que o problema inicial diz que temos que pegar pelo menos um valor do vetor, então se todos os elementos em 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 sejam negativos, a resposta será .
Problemas para praticar
Agora é a sua vez! Tente fazer esses problemas que usam os algoritmos ensinados na aula de hoje ou ideias semelhantes: