Algoritmo para encontrar a diferença máxima entre dois elementos de um array

Embora sejam uma das estruturas de dados mais simples no que tange à implementação e utilização, os arrays estão presentes na resolução de inúmeros desafios de programação. A pesquisa pelo elemento majoritário, a busca pelo índice de equilíbrio e a remoção de elementos duplicados são uma pequena amostra do vasto catálogo de algoritmos dos vetores.

Neste artigo, os detalhes que envolvem o cálculo da diferença máxima entre dois elementos de um array serão devidamente discorridos. Além disso, com o intuito de promover uma análise de algoritmos mais bem elaborada, haverá um comparativo entre as soluções com complexidade de tempo linear e quadrática.

Entendendo o problema

A princípio, a compreensão do problema para encontrar a diferença máxima entre dois elementos de um vetor aparenta ser óbvia. Entretanto, cabe ressaltar a presença de uma premissa importante, que impacta diretamente no desenvolvimento do algoritmo em questão.

De modo a determinar a diferença máxima, há uma regra que deve ser obrigatoriamente obedecida. Essa pré-condição estabelece que as operações de subtração no array só podem ser efetuadas entre elementos de índices maiores e menores (j > i). Ou seja, não é permitido subtrair um item localizado no índice zero do vetor com outro que esteja no índice dois, por exemplo. 

Supondo que houvesse a necessidade de calcular a diferença máxima para o array [2, 5, 1, 10, 3, 7], as seguintes subtrações estariam autorizadas no contexto do algoritmo.

• (5 - 2) = 3
• (1 - 2) = -1
• (10 - 2) = 8
• (3 - 2) = 1
• (7 - 2) = 5
• (1 - 5) = -4
• (10 - 5) = 5
• (3 - 5) = -2
• (7 - 5) = 2
• (10 - 1) = 9
• (3 - 1) = 2
• (7 - 1) = 6
• (3 - 10) = -7
• (7 - 10) = -3
• (7 - 3) = 4

Conforme destacado, nove é a diferença máxima resultante do vetor [2, 5, 1, 10, 3, 7]. Para obter esse valor, subtraiu-se os números dos índices três e dois da estrutura, estando portanto de acordo com a normativa j > i.

Usando complexidade quadrática de tempo para resolver o problema

A maneira trivial de definir a diferença máxima de um array se baseia na execução de loops aninhados. Enquanto o laço externo fixa em somente um elemento, a estrutura de repetição interna percorre os demais itens do vetor. A cada iteração, subtrai-se os números nos índices j e i, e a maior diferença encontrada até então é armazenada.

Evidentemente, este algoritmo apresenta uma complexidade quadrática de tempo. A justificativa para isso reside no fato de que ambos os loops da função dependem da quantidade de elementos do vetor passado como input.

Os pormenores da lógica por trás da solução estão elencados abaixo.

1. A variável diferencaMaxima é declarada para manipular o resultado da maior subtração localizada no array arr durante o andamento do algoritmo.
2. O primeiro loop itera por todos os elementos do vetor arr, iniciando a varredura a partir do item presente no índice zero. 
3. Em contrapartida, o loop aninhado começa a sua iteração no índice posterior ao do laço externo. Desse jeito, a comparação dos elementos nos índices j e i satisfaz a condição de diferença (j > i) proposta pelo problema.
4. No decorrer das iterações do loop aninhado, os itens dos índices j e i são subtraídos, com a finalidade de verificar se o resultado desta operação supera o valor armazenado na variável diferencaMaxima. Caso isso seja verdade, significa que uma nova diferença máxima foi calculada para o array arr.
5. Após os laços terem sido percorridos, a função retorna o valor contido na variável diferencaMaxima.

Usando complexidade linear de tempo para resolver o problema

O algoritmo de complexidade linear de tempo simplifica e otimiza a solução de diferença máxima, eliminando a necessidade do uso de laços aninhados. Para alcançar isso, temos o emprego de um raciocínio inteligente na função que resolve o problema.

A partir de uma reflexão cuidadosa, podemos concluir que o produto da diferença máxima de qualquer vetor sempre envolverá o menor elemento desta estrutura de dados. Logo, a identificação do número de menor valor no array permite encontrar de um modo muito mais eficaz a resposta sendo procurada.

O passo a passo para entender os fundamentos do código está especificado a seguir. 

1. Assim como no algoritmo de complexidade quadrática, a variável diferencaMaxima é declarada para manipular o resultado da maior subtração localizada no array arr durante o andamento do algoritmo.
2. A variável menorElemento é declarada para armazenar o menor número do vetor arr que será utilizado no cálculo de diferença máxima.
3. O único loop da função percorre o array arr em sua totalidade, realizando duas verificações a cada iteração. A primeira delas checa se a subtração do elemento atual com o menor item localizado até o presente momento supera a diferença máxima vigente. Já a segunda condicional valida se o elemento atual é o menor número varrido na estrutura.
4. Depois do laço ser percorrido, o método retorna o valor da variável diferencaMaxima.

Analisando a complexidade das soluções

O detalhamento a respeito dos algoritmos de diferença máxima demonstrou que a primeira função analisada possui uma complexidade de tempo quadrática, tendo em vista a existência de loops aninhados sensíveis à variação do input.

Por outro lado, a segunda função dispõe de uma complexidade de tempo linear, pois os elementos do vetor de input são percorridos apenas uma vez. Aliás, segundo estatísticas geradas pelo framework BenchmarkDotNet, o ganho de performance do algoritmo quando comparado à solução quadrática é extremamente notório.

Método	Input	Média de tempo	Espaço alocado
MétodoComplexidadeLinear	InputInt32[18]	Média de tempo19.37 ns	Espaço alocado-
MétodoComplexidadeQuadratica	InputInt32[18]	Média de tempo145.48 ns	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[40]	Média de tempo36.37 ns	Espaço alocado-
MétodoComplexidadeQuadratica	InputInt32[40]	Média de tempo838.64 ns	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[80]	Média de tempo67.70 ns	Espaço alocado-
MétodoComplexidadeQuadratica	InputInt32[80]	Média de tempo3,650.50 ns	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[142]	Média de tempo139.49 ns	Espaço alocado-
MétodoComplexidadeQuadratica	InputInt32[142]	Média de tempo11,047.44 ns	Espaço alocado-

A disparidade no tempo de execução dos algoritmos pode ser constatada logo com os inputs menores. Para vetores de dezoito elementos, o MétodoComplexidadeLinear levou em média 19.37 ns de processamento, enquanto o MétodoComplexidadeQuadratica gastou em média 145.48 ns, cerca de sete vezes mais.

Os números ficam ainda mais assustadores quando comparamos o cenário com cento e quarenta e dois itens no array. A função linear apresenta uma vantagem na casa de setenta e nove vezes. Além disso, partindo do caso com menos elementos (dezoito) para o com mais elementos (cento e quarenta e dois), o MétodoComplexidadeLinear possuiu um aumento de apenas 120.12 ns. Já o MétodoComplexidadeQuadratica registrou 10901.96 ns de crescimento.

O código-fonte completo dos algoritmos e os detalhes extras a respeito da performance de cada um deles estão disponíveis no meu repositório do Github.