Algoritmo para encontrar o tamanho do subarray ímpar-par mais longo

O cálculo da diferença máxima entre dois elementos, a busca pelo item majoritário e a computação do índice de equilíbrio integram o vasto conjunto de problemas que são resolvidos a partir da aplicabilidade dos arrays. Essas estruturas de dados estão presentes em praticamente todas as linguagens de programação, permitindo um fácil acesso e simples manipulação das informações fornecidas pelo usuário.

Com o intuito de expandir o catálogo de algoritmos para vetores, duas soluções serão discutidas no discorrer deste artigo, as quais têm o propósito de encontrar o tamanho do maior subarray ímpar-par em qualquer estrutura. Como de praxe, haverá diferenças e comparativos de performance entre as funções apresentadas.

Entendendo o problema

Dado um array de N números inteiros, o objetivo deste desafio consiste em achar o total de itens do maior subarray ímpar-par. Por definição, um subarray equivale à uma parte do vetor principal, sendo que a sua capacidade mínima é de um elemento, e a capacidade máxima de N elementos.

De modo a elucidar o parágrafo anterior, considere um array hipotético composto pelos números [3, 4, 5, 7, 8]. Essa coleção de itens origina quatorze subarrays, que estão representados a seguir.

• [3]
• [3, 4]
• [3, 4, 5]
• [3, 4, 5, 7]
• [3, 4, 5, 7, 8]
• [4]
• [4, 5, 7]
• [4, 5, 7, 8]
• [5]
• [5, 7]
• [5, 7, 8]
• [7]
• [7, 8]
• [8]

Averiguando cada subarray gerado, a estrutura que contém a maior quantidade de alternâncias entre números ímpares e pares é a terceira, formada pelos elementos [3, 4, 5]. Com isso, o tamanho do subarray ímpar-par mais longo neste exemplo se limita a três itens.

Usando complexidade quadrática de tempo para resolver o problema

Conceito popular nos debates que envolvem algoritmos, a abordagem força bruta ajuda na resolução de inúmeros problemas, desde os mais fáceis até os mais dificeís. Entretanto, como o próprio nome sugere, as funções que se fazem valer dessa técnica acabam por ter um desempenho frágil, pois elas testam todas as possibilidades até chegar em uma resposta definitiva.

Geralmente, os algoritmos de força bruta são classificados com complexidade quadrática de tempo. A razão para isso reside no fato de que esse método algorítmico percorre os vetores e outras estruturas de dados por meio de loops aninhados, verificando os mesmos elementos repetidamente.

A função destacada acima obtém a capacidade do maior subarray ímpar-par justamente através da estratégia da força bruta, varrendo subarray por subarray para retornar o resultado correto.

1. A variável tamanho é declarada para armazenar a quantidade de itens do subarray ímpar-par mais longo.
2. O primeiro loop da função itera por todos os elementos do vetor a, inicializando a cada laço uma variável contador, que por sua vez controla a quantidade de itens do subarray ímpar-par examinado na iteração atual.
3. O loop aninhado também faz a varredura completa do array a, verificando se o item percorrido na iteração anterior é ímpar, e se o item varrido na iteração atual é par, e vice-versa. Caso essa condição demonstre ser verdadeira, a variável contador recebe um incremento, indicando que uma alternância de números pares e ímpares foi identificada.
4. Após a execução do segundo loop, a variável tamanho é atualizada de acordo com o último valor atribuído à contador. Ou seja, se a varredura anterior pelo loop aninhado localizou um subarray ímpar-par de capacidade maior, tamanho passa a receber o conteúdo de contador.
5. Depois de checar cada subarray existente do vetor a, a função verifica se a variável tamanho possui o seu valor igual a um. Isso significa que nenhuma alternância entre números pares e ímpares foi encontrada durante a aplicação do algoritmo. Em cenários desse tipo, o método retorna zero como a capacidade do subarray ímpar-par.
6. Enfim, caso a variável tamanho tenha registrado um valor superior a um, o seu conteúdo é retornado pela função, indicando portanto a quantidade total de itens do maior subarray ímpar-par.

Usando complexidade linear de tempo para resolver o problema

Por via de regra, uma função que siga originalmente o princípio da força bruta pode ser otimizada em termos de eficiência. Os algoritmos com essa característica costumam ser convertidos em rotinas de complexidade linear de tempo, eliminando quaisquer laços aninhados ou outras estruturas que degradem a sua execução.

A fim de reduzir a complexidade de tempo, a função ilustrada se faz valer de um raciocínio inteligente para determinar o tamanho do maior subarray ímpar-par. A ideia central do algoritmo está concentrada na relação entre os elementos atual e anterior do vetor a ser percorrido.

Caso ambos sejam números pares ou ímpares, evidentemente há uma interrupção na sequência do subarray ímpar-par. Por outro lado, as circunstâncias mudam se um elemento for par e o outro ímpar, dando início assim à cadeia de números procurada no problema.

1. Se o array não possuir elementos, a função retorna zero como a capacidade do subarray ímpar-par.
2. A variável maiorTamanho é declarada para armazenar a capacidade do maior subarray ímpar-par encontrado.
3. A variável tamanhoAtual é declarada para armazenar a capacidade do subarray ímpar-par sendo varrido na iteração atual.
4. O único loop da função percorre todos os itens do vetor a. A cada laço, o método garante se o elemento atual é par, e se o elemento anterior é ímpar, e vice-versa. Quando essa condição é verdadeira, a variável tamanhoAtual recebe um incremento, indicando a presença de um subarray ímpar-par. Entretanto, se a verificação for falsa, a variável maiorTamanho tem o seu valor atualizado de acordo com a quantidade registrada em tamanhoAtual. Além disso, a própria variável tamanhoAtual passa por uma redefinição do seu valor, demarcando o fim do subarray ímpar-par atual.
5. Por fim, a função retorna o valor da variável maiorTamanho, caso um subarray ímpar-par tenha sido localizado na estrutura do vetor a.

Analisando a complexidade das soluções

Conforme pormenorizado nas seções anteriores do artigo, no que diz respeito a complexidade de tempo, o primeiro algoritmo ostenta uma complexidade quadrática devido à varredura de loops aninhados, enquanto o segundo algoritmo manifesta uma complexidade linear em virtude da única iteração realizada no vetor de input. 

Já sobre o uso do espaço auxiliar de memória, as duas funções apresentam uma complexidade constante, pois declaram somente variáveis simples de controle. Além disso, não possuem chamadas recursivas que ocupem a pilha de chamadas do programa.

Método	Input	Média de tempo	Espaço alocado
MétodoComplexidadeLinear	InputInt32[10]	Média de tempo20.80 ns	Espaço alocado-
MétodoComplexidadeQuadratica	InputInt32[10]	Média de tempo40.20 ns	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[50]	Média de tempo105.74 ns	Espaço alocado-
MétodoComplexidadeQuadratica	InputInt32[50]	Média de tempo195.11 ns	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[100]	Média de tempo214.49 ns	Espaço alocado-
MétodoComplexidadeQuadratica	InputInt32[100]	Média de tempo380.24 ns	Espaço alocado-
MétodoComplexidadeLinear	InputInt32[200]	Média de tempo438.82 ns	Espaço alocado-
MétodoComplexidadeQuadratica	InputInt32[200]	Média de tempo750.02 ns	Espaço alocado-

As estatísticas produzidas pela biblioteca BenchmarkDotNet permitem visualizar com maior precisão a disparidade na execução das funções. Para um input de dez elementos, o MétodoComplexidadeQuadratica consome praticamente o dobro de tempo. Essa métrica é reduzida levemente a partir dos cinquenta itens, porém o MétodoComplexidadeLinear continua sendo muito mais performático.

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.