Problema: Subsequência de Soma Máxima

Olá pessoal, tudo bem?

Decidi começar a trazer posts de problemas de programação. Os posts vão funcionar da seguinte forma:

• Definir o problema
• Falar sobre o problema
• Mostrar as soluções

Problema: Achar a subsequência de soma máxima de uma sequência S.

Sobre o problema: Tendo uma sequência S, temos que encontrar uma subsequência dela que tenha a maior soma possível entre todas as subsequências existentes de S. Agora, suponha que temos a sequência S abaixo:

S = {-1, 2, -4, 2, -1, 3, -4, 5}

Existem várias subsequências de S, algumas delas são:

{-1, 2} -> soma = 3

{2, -1, 3} -> soma = 4

{5} -> soma = 5

Solução: Para resolver este problema, temos um algoritmo famoso chamado de algoritmo de Kadane. A ideia é percorrer o vetor sempre guardando a soma máxima do segmento que você ta estudando e a maior soma de todos os segmentos vistos. Segue o link do código em C++: kadane.cpp.

Simulação do algoritmo: Vamos simular o algoritmo para a sequência S:

Teremos 2 variáveis, maxTotal e maxAtual. A maxAtual vai sempre guardar o máximo da sequência que estamos estudando no momento e o maxTotal vai guardar o máximo total das sequências que foram estudadas.

Momento 1:

S = {-1, 2, -4, 2, -1, 3, -4, 5}

maxAtual = 0

maxTotal = 0

Momento 2: Vamos percorrer a sequência e chamar de s a subsequẽncia que estamos estudando.

Note que não alteramos o valor de maxAtual pois o elemento estudado tem soma menor que maxAtual.

s = {-1}

maxAtual = 0

maxTotal = 0

Momento 3: 

s = {2}

maxAtual = 2

maxTotal = 2

Momento 4: Veremos que a subsequência estudada agora tem soma negativa. Sendo assim, o valor de maxAtual se torna zero.

s = {2, -4}

maxAtual = 0

maxTotal = 2

Momento 5: 

s = {2}

maxAtual = 2

maxTotal = 2

Momento 6: Aqui vemos que o valor do maxAtual diminuiu, porém não foi zerado. Isso se deve a que, se um número positivo vier, teremos uma subsequência de soma maior caso este segmento abaixo continue participando.

s = {2, -1}

maxAtual = 1

maxTotal = 2

Momento 7: Aqui podemos ver que a subsequência {2, -1, 3} tem soma maior que somente {3}!

s = {2, -1, 3}

maxAtual = 4

maxTotal = 4

Momento 8: A soma da subsequẽncia atual foi zerada.

s = {2, -1, 3, -4}

maxAtual = 0

maxTotal = 4

Momento 9:

s = {5}

maxAtual = 5

maxTotal = 5

Simulado! 

Isso é tudo por hoje. Trarei mais algoritmos desse nível futuramente. Caso queiram que eu fale sobre algum, podem colocar nos comentários!