Técnicas de Programação - Soma Máxima em Intervalo

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$ .

	// Curso NOIC de Informática - Técnicas de Programação - Soma máxima em intervalo
	// Algoritmo de Kadane
	// Escrito por Arthur Lobo

	#include<bits/stdc++.h>
	using namespace std;
	const int infinito = 1000000000;
	const int maxn = 5e5+10;

	int n, a[maxn];

	int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
	cin >> a[i];
	}
	int soma = 0; // comecamos a soma como 0
	int resp = -infinito;
	for(int i = 1; i <= n; i++) {
	// sempre que o intervalo terminando em i-1
	// for menor que 0, resetamos ele para 0
	if(soma < 0) soma = 0;
	soma+= a[i];
	resp = max(resp,soma);
	}
	cout << resp << endl;

	}

view raw Kadane.cpp hosted with

by GitHub

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$ .

	// Curso NOIC de Informática - Técnicas de Programação - Soma máxima em intervalo
	// Soma de Prefixo
	// Escrito por Arthur Lobo

	#include<bits/stdc++.h>
	using namespace std;
	const int infinito = 1000000000;
	const int maxn = 5e5+10;

	int n, a[maxn], s[maxn];

	int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
	cin >> a[i];
	s[i] = s[i-1]+a[i];
	}
	int menor = 0; // comecamos menor como S[0], ou seja, 0
	int resp = -infinito;
	for(int i = 1; i <= n; i++) {
	// vemos se s[i-1] é < que menor,
	// se for, o substituimos
	menor = min(menor,s[i-1]);
	resp = max(resp,s[i]-menor);
	}
	cout << resp << endl;
	}

view raw Soma maxima em intervalo com Soma de Prefixo.cpp hosted with

by GitHub

Problemas para praticar

Agora é a sua vez! Tente fazer esses problemas que usam os algoritmos ensinados na aula de hoje ou ideias semelhantes: