Algoritmo para encontrar o Subarray de soma máxima

No campo dos algoritmos e estruturas de dados, desafios que demandam o uso de arrays são muito comuns. Em entrevistas de empregos para multinacionais como o Google e a Microsoft, problemas envolvendo essa estrutura costumam ser recorrentes.

Aliás, um dos exercícios mais populares consiste de encontrar o Subarray de soma máxima. Dentro dos limites de um vetor, qualquer elemento ou conjunto de elementos contíguos podem formar um Subarray. Por exemplo, o array hipotético arr, composto pelos itens 1, 2 e 3, apresenta seis Subarrays possíveis.

• [1]
• [2]
• [3]
• [1, 2]
• [2, 3]
• [1, 2, 3]

Logo, tendo como referência os Subarrays dispostos acima, o último possui a maior soma geral, totalizando uma contagem de seis.

Indiscutivelmente, a partir do momento que surge a necessidade de calcular o resultado em questão através de um algoritmo, as soluções não são tão óbvias e divergem de modo considerável entre si em relação à performance.

Nesta publicação, examinaremos duas funções, uma delas detendo complexidade quadrática de tempo, e a outra complexidade linear de tempo.

Entendendo o problema

Ainda que na introdução do artigo tenham sido explicados os conceitos de um Subarray e a ideia geral por trás do problema, cabe analisar um cenário mais complexo, visando a assimilação do desafio proposto.

Conjecture a existência de um array que armazene os elementos -4, 5, 2, -1, 3, 0, -2 e 6. Os Subarrays oriundos desse arranjo seriam os seguintes.

• [-4]
• [5]
• [2]
• [-1]
• [3]
• [0]
• [-2]
• [6]
• [-4, 5]
• [-4, 5, 2]
• [-4, 5, 2, -1]
• [-4, 5, 2, -1, 3]
• [-4, 5, 2, -1, 3, 0]
• [-4, 5, 2, -1, 3, 0, -2]
• [-4, 5, 2, -1, 3, 0, -2, 6]
• [5, 2]
• [5, 2, -1]
• [5, 2, -1, 3]
• [5, 2, -1, 3, 0]
• [5, 2, -1, 3, 0, -2]
• [5, 2, -1, 3, 0, -2, 6]
• [2, -1]
• [2, -1, 3]
• [2, -1, 3, 0]
• [2, -1, 3, 0, -2]
• [2, -1, 3, 0, -2, 6]
• [-1, 3]
• [-1, 3, 0]
• [-1, 3, 0, -2]
• [-1, 3, 0, -2, 6]
• [3, 0]
• [3, 0, -2]
• [3, 0, -2, 6]
• [0, -2]
• [0, -2, 6]
• [-2, 6]

Contabilizando meticulosamente o montante de cada Subarray listado, conclui-se que a estrutura [5, 2, -1, 3, 0, -2, 6] engloba o total máximo de todos os Subarrays, com uma soma resultante de treze.

Na circunstância de dois ou mais Subarrays terem uma somatória idêntica, qualquer Subarray escolhido será uma resposta válida.

Usando complexidade quadrática de tempo para resolver o problema

Antes de destrinchar a solução com a melhor complexidade de tempo, vale a pena entender um dos algoritmos mais simples para resolver este problema. Embora a função a seguir não seja performática para inputs maiores, dispondo de uma complexidade quadrática, ela servirá de base para o algoritmo de complexidade linear.

Quase que de imediato, especialmente para quem está acostumado a estudar algoritmos, perceberá que o loop aninhado com a condição if caracteriza a complexidade quadrática do método. Isso porque o laço percorre o vetor em sua totalidade, analogamente ao loop mais externo.

De forma concisa, os passos que integram o algoritmo estão especificados na listagem abaixo.

1. A variável indiceFinal é declarada para armazenar o último índice do Subarray de soma máxima.
2. A variável maiorSomaResultado é declarada para armazenar a contabilidade do Subarray de soma máxima.
3. O loop for externo é acionado para percorrer todos os elementos do array arr. A cada iteração, este laço define uma variável identificada como maiorSomaAtual, que controla a soma de elementos do Subarray sendo percorrido no momento.
4. Aninhado ao loop externo, o segundo laço de repetição for percorre novamente o vetor em sua totalidade, atualizando o valor da variável maiorSomaAtual. Para finalizar o seu processo, o loop verifica a cada iteração se a maiorSomaAtual supera o valor contido em maiorSomaResultado. Em caso afirmativo, isso significa que o Subarray atual possui uma soma maior. Consequentemente, os valores das variáveis maiorSomaResultado e indiceFinal são modificados.
5. A variável indiceInicial é declarada para armazenar o primeiro índice do Subarray de soma máxima.
6. O loop while é executado com o objetivo de localizar o valor da variável indiceInicial. Para isso, de iteração em iteração, o laço subtrai o valor de maiorSomaResultado do elemento atual sendo percorrido. Quando essa variável for zerada, significa que o indiceInicial foi encontrado com sucesso.
7. Um último loop for itera entre o indiceInicial e o indiceFinal para exibir os elementos do Subarray.

Usando complexidade linear de tempo para resolver o problema

Conforme a teoria de análise de algoritmos, funções que possuam uma complexidade linear de tempo levam vantagem em detrimento das com complexidade quadrática de tempo, sobretudo para inputs maiores. E, na maioria das vezes, uma solução pode ser convertida em uma complexidade de performance superior, não sendo diferente com este algoritmo do Subarray.

Esmiuçando a rotina em evidência, percebe-se facilmente que a lógica por trás dela incorpora muitas semelhanças com a função anterior. Contudo, agora o código está estruturado de tal forma que a sua execução tenha uma complexidade linear de tempo, seguindo também a definição do Algoritmo de Kadane.

1. A variável indiceFinal é declarada para armazenar o último índice do Subarray de soma máxima.
2. A variável maiorSomaAtual é declarada para armazenar a contabilidade do Subarray de soma máxima da iteração atual.
3. A variável maiorSomaResultado é declarada para armazenar a contabilidade do Subarray de soma máxima definitivo.
4. O loop for, começando da segunda posição do array, verifica a cada iteração se o elemento atual é maior do que a soma dele com os itens contabilizados na variável maiorSomaAtual. Se essa condição for verdadeira, indicando que um novo Subarray de soma máxima foi encontrado, as variáveis maiorSomaResultado e indiceFinal são atualizadas.
5. A variável indiceInicial é declarada para armazenar o primeiro índice do Subarray de soma máxima.
6. O loop while é executado para descobrir o valor da variável indiceInicial. Assim, a cada iteração, o laço subtrai o valor de maiorSomaResultado do elemento atual sendo percorrido. Quando essa variável for zerada, significa que o indiceInicial foi encontrado com sucesso.
7. O último loop for itera entre o indiceInicial e o indiceFinal para mostrar os itens do Subarray.

Analisando a complexidade das soluções

Até aqui, após uma análise cuidadosa das duas funções, foi possível antecipar as suas respectivas complexidades de tempo. Enquanto o primeiro algoritmo se situa no grupo da complexidade quadrática, percorrendo de maneira aninhada os elementos do array de input, o segundo algoritmo aperfeiçoou a solução original, assumindo uma complexidade linear.

Porém, o uso do espaço auxiliar de memória precisa ser investigado do mesmo modo. No caso de ambos os algoritmos, essa complexidade pode ser classificada como constante, afinal de contas nenhum deles apresenta chamadas recursivas ou estruturas de dados adicionais atreladas à variação do input.

Com o intuito de visualizar na prática as complexidades descritas, os indicadores de execução dos métodos foram gerados através da biblioteca BenchmarkDotNet. 

Método	Input	Média de tempo	Espaço alocado
MétodoComplexidadeLinear	InputInt32[10]	Média de tempo20.55 μs	Espaço alocado256 B
MétodoComplexidadeQuadratica	InputInt32[10]	Média de tempo20.24 μs	Espaço alocado256 B
MétodoComplexidadeLinear	InputInt32[50]	Média de tempo103.23 μs	Espaço alocado1568 B
MétodoComplexidadeQuadratica	InputInt32[50]	Média de tempo101.96 μs	Espaço alocado1568 B
MétodoComplexidadeLinear	InputInt32[100]	Média de tempo254.74 μs	Espaço alocado3200 B
MétodoComplexidadeQuadratica	InputInt32[100]	Média de tempo291.36 μs	Espaço alocado3200 B
MétodoComplexidadeLinear	InputInt32[500]	Média de tempo1,233.76 μs	Espaço alocado15873 B
MétodoComplexidadeQuadratica	InputInt32[500]	Média de tempo1,382.02 μs	Espaço alocado15873 B

Considerando os cenários de teste, a função ComplexidadeQuadratica obteve melhores resultados somente para os inputs menores de dez e cinquenta elementos. Mesmo assim, se compararmos com o algoritmo ComplexidadeLinear, a diferença de tempo foi irrisória. Todavia, logo que o input cresceu razoavelmente para cem e quinhentos itens, o procedimento ComplexidadeLinear passou a ter um melhor desempenho.

O código-fonte dos algoritmos está disponível na íntegra no meu repositório do Github.