Sublista contígua de soma máxima

Origem: Wikipédia, a enciclopédia livre.

Em Ciência da Computação, encontrar a sublista contígua de maior soma a partir de uma lista de números é um problema bastante conhecido.

 10   5   -17   20   50   -1   3   -30   10 

Na seqüência acima, a sublista contígua de maior soma é [20, 50, -1, 3] e a soma total desse trecho é 72.

Tipicamente, a lista de números a ser computada como entrada deve ter números positivos e negativos. Dessa forma, ao encontrar um número negativo vizinho a uma sublista de maior soma computada até então, uma das dificuldades do problema no decorrer da sua resolução é avaliar se esse número negativo deve ser acrescido à sublista ou não. Essa avaliação é necessária porque depois de um número negativo poderão vir na seqüência um ou mais números positivos que compensem o decréscimo resultante da inclusão daquele número negativo. Por outro lado, esse mesmo número negativo vizinho poderá não ser incorporado à sublista de maior soma, pois o resultado final seria uma soma menor do que a obtida até então.

Para uma lista que contenha apenas números positivos, o resultado de maior soma será simplesmente a lista inteira dada como entrada.

Nos algoritmos que serão apresentados a seguir, quando uma lista de números negativos é dada como entrada ou ainda se uma sublista parcial computada ao longo da resolução do problema resultar numa soma negativa, o resultado deverá ser zero, ou seja, o equivalente a obter como resposta uma lista vazia.

Histórico[editar | editar código-fonte]

O problema da soma máxima a partir de uma lista de números teve origem numa versão bidimensional mais complexa de um problema de emparelhamento de padrões inicialmente apresentado por Ulf Grenander, da Brown University.

Ao perceber que o algoritmo cúbico era impraticável para a resolução da versão unidimensional mais simples do problema de identificação de sequências contínuas de maior soma, Grenander desenvolveu a versão quadrática do algoritmo. Posteriormente, Michael Shamos, da atual Carnegie-Mellon University, desenvolveu em 1977 a versão sub-quadrática do algoritmo por divisão e conquista.

Por fim, o estatístico Jay Kadane, da mesma universidade de Shamos, desenvolveu dias depois a versão linear do algoritmo para o problema da sublista contígua de maior soma. Esse algoritmo permanece até os dias atuais como a versão mais eficiente e a melhor solução possível, pois qualquer algoritmo que pretenda resolver o problema em estudo deve necessariamente percorrer os N elementos da lista dada como entrada.

Quatro algoritmos para o problema da sublista contígua de soma máxima[editar | editar código-fonte]

Algoritmo cúbico[editar | editar código-fonte]

O primeiro algoritmo percorre todo o espaço de soluções do problema encontrando uma a uma todas as sublistas contíguas possíveis de serem obtidas a partir de uma lista inicial dada e retornando a sublista de maior soma conforme desejado. No entanto, a cada passo durante sua execução a computação de uma sublista seguinte é reiniciada do zero, ou seja, os cálculos efetuados para se obter um resultado parcial ao longo da resolução do problema não são reaproveitados no cômputo da solução parcial seguinte do mesmo problema.

def algoritmo_cubico(X):
    max_ate_agora = 0.0
    N = len(X)
    for L in range(1, N + 1):
        for U in range(L, N + 1):
            soma = 0.0
            for I in range(L, U + 1):
                soma = soma + X[I - 1]
            max_ate_agora = max(max_ate_agora, soma)
    return max_ate_agora

Algoritmo Cúbico (em Python)

A computação de todas as sublistas possíveis é realizada através de 3 loops aninhados, onde o primeiro é executado exatamente N vezes e o segundo e terceiro loop podem ser executados até N vezes cada um (N é o número de elementos da lista dada como entrada).

Utilizando a notação Big-Oh para análise do tempo de execução do algoritmo, tem-se que cada loop do mesmo tem custo O(N), totalizando um tempo de execução de nesse primeiro algoritmo.

Apesar de correto, o algoritmo cúbico apresentado é lento e torna-se inviável para entradas maiores, conforme apresentado no tópico “testes realizados”. No algoritmo cúbico pode-se dizer que a estratégia adotada foi a de 'força bruta', ou seja, calcular uma a uma as possíveis soluções e retornar a melhor sem se preocupar com o uso de estratégias auxiliares de minimização do esforço computacional necessário para obtenção da solução final.

Algoritmo quadrático[editar | editar código-fonte]

O segundo algoritmo utiliza a técnica de armazenagem de resultados intermediários para evitar recomputação. Beneficiando-se do fato de que duas somas parciais vizinhas computadas ao longo da execução diferem por apenas um elemento, é possível reaproveitar os cálculos efetuados num determinado passo do algoritmo no passo imediatamente seguinte. Explicitando os intervalos, duas somas parciais vizinhas podem ser representadas por X[L ... U] e X[L ... U – 1].

def algoritmo_quadratico(X):
    max_ate_agora = 0.0
    N = len(X)
    for L in range(1, N + 1):
        soma = 0.0
        for U in range(L, N + 1):
            soma = soma + X[U - 1]
            max_ate_agora = max(max_ate_agora, soma)
    return max_ate_agora

Algoritmo Quadrático (em Python)

Analisando o tempo de execução do algoritmo, tem-se que o primeiro loop é executado N vezes e o segundo loop pode ser executado até N vezes, totalizando um tempo de execução de .

A técnica de armazenar estados utilizada pelo algoritmo quadrático no intuito de evitar a recomputação utiliza mais espaço, porém gasta menos tempo na comparação com o algoritmo cúbico.

Uma variação do algoritmo quadrático

Utilizando a técnica de pré processamento de informações em uma estrutura de dados auxiliar a qual computa inicialmente num array (‘acumulado’) as somas acumuladas dos valores em X[1 ... I] para depois reaproveitá-las no loop seguinte, também é possível obter um tempo de execução total de .

def algoritmo_quadratico_v2(X):
    N = len(X)
    acumulado = [0.0]
    for I in range(1, N + 1):
        acumulado.append(0.0)
    acumulado[0] = X[0]
    for I in range(2, N + 1):
        acumulado[I - 1] = acumulado[I - 2] + X[I - 1]
    max_ate_agora = 0.0
    for L in range(1, N + 1):
        soma = 0.0
        for U in range(L, N + 1):
            if L == 1:
                soma = acumulado[U - 1]
            else:
                soma = acumulado[U - 1] - acumulado[L - 2]
            max_ate_agora = max(max_ate_agora, soma)
    return max_ate_agora

Variação do Algoritmo Quadrático (em Python)

A partir do array construído inicialmente onde cada elemento é uma soma acumulada, é possível computar a soma dos valores em X[L ... U] por: acumulado [U] – acumulado[L – 1].

Obs.: Na implementação em Python logo acima, os índices das listas estão decrescidos por 1 (ou seja, [U – 1] e [L – 2]), pois essa linguagem considera [0] como o primeiro elemento de uma lista, [1] como o segundo e assim sucessivamente.

Os dois algoritmos quadráticos apresentados nesse tópico têm seu tempo de execução da ordem de , pois os mesmos inspecionam todos os possíveis pares de elementos iniciais e finais na composição das sublistas possíveis de serem obtidas e avaliam a soma dos elementos nesses intervalos. Como existem O(N2) dessas listas, o tempo de execução de algoritmos que utilizem essa mesma estratégia deverá ser sempre quadrático.

Uma solução por divisão e conquista[editar | editar código-fonte]

O algoritmo abaixo é ainda mais rápido que o anterior e faz uso da seguinte estratégia comum adotada por outros algoritmos que trabalham por “Divisão e Conquista”:

Para resolver um problema de tamanho N, resolva recursivamente 'b' problemas de tamanho aproximado N/b e combine suas soluções para obter a resposta da versão completa do problema.

Inicialmente, a lista de tamanho N é divida em dois subproblemas de tamanho aproximado N/2, os quais serão chamados respectivamente de A e B.

Depois, recursivamente o algoritmo vai encontrar a maior sublista contígua em A (max_A) e a maior sublista contígua em B (max_B).

Visualização da execução do algoritmo de divisão e conquista em uma lista de 4 elementos
def lista_entrada(X):
    def algoritmo_divisao_e_conquista(L, U):
        if L > U:
            return 0.0
        if L == U:
            return max(0.0, X[L - 1])
           
        M = (L + U) / 2
        soma = 0.0
        max_a_esquerda = 0.0
        for I in range(M, 0, -1):
            soma = soma + X[I - 1]
            max_a_esquerda = max(max_a_esquerda, soma)
        soma = 0.0
        max_a_direita = 0.0
        for I in range(M + 1, U + 1):
            soma = soma + X[I - 1]
            max_a_direita = max(max_a_direita, soma)
        max_C = max_a_esquerda + max_a_direita
                   
        max_A = algoritmo_divisao_e_conquista(L, M)
        max_B = algoritmo_divisao_e_conquista(M + 1, U)
        return max(max_C, max_A, max_B)
    N = len(X)
    resposta = algoritmo_divisao_e_conquista(1, N)
    return resposta

Algoritmo por divisão e conquista (em Python)

No entanto, a maior sublista contígua também pode estar parte em A e parte em B, o que será computado pela variável max_C. Para a computação de max_C, é utilizado o fato de que sua maior parte em A deve começar exatamente na extremidade direita de A (a qual faz fronteira com B) e avançar para dentro da parte A e da mesma forma a maior parte em B deve começar na extremidade de B que faz fronteira com A e avançar para dentro da parte B. Assim, max_C corresponderá à soma dessas duas maiores partes definidas anteriormente.

No caso base do algoritmo, é tratado o caso da menor sublista possível, a qual corresponde à de apenas um elemento e nesse caso a maior soma é o próprio elemento ou zero se o mesmo for negativo. Ainda no caso base, também é dado o tratamento para o caso da lista vazia, ou seja, com nenhum elemento. Nesse caso, a saída é definida como zero.

O tempo de execução do algoritmo de divisão e conquista é , significativamente mais rápido que o algoritmo quadrático anteriormente apresentado. Esse tempo de execução advém do fato de que o algoritmo faz O(N) operações a cada nível das chamadas recursivas e o número de níveis corresponde a O(log N), a altura de uma árvore binária completa resultante das sucessivas divisões por 2 do problema inicial e dos subproblemas gerados a cada chamada recursiva.

Solução linear[editar | editar código-fonte]

Para atingir um tempo de execução de O(N) para a resolução do mesmo problema que inicialmente foi computado por um algoritmo de desempenho muito mais lento (O(N3)), utiliza-se uma solução que percorre a lista de números do início ao fim mantendo o cômputo das maiores somas parciais. No algoritmo apresentado a seguir, quando chegarmos ao último elemento da lista a resposta para o problema estará dada.

Supondo que num dado momento o problema esteja resolvido para a lista X[1 ... I - 1], estende-se a solução em direção ao elemento seguinte da lista utilizando o seguinte raciocínio: ou a nova solução corresponde à maior soma entre os primeiros 'I – 1' elementos (a qual será chamada de max_ate_agora) ou então a solução será alguma sublista cujo término inclui 'I ' como último elemento (max_terminando_aqui).

Se a variável max_terminando_aqui fosse computada do zero a cada passo do algoritmo, ter-se-ia novamente um algoritmo quadrático. No entanto, salvando-se o estado parcial dessa variável de forma semelhante à técnica que foi adotada no primeiro algoritmo quadrático apresentado para evitar a recomputação entre as somas parciais até se ter a soma máxima em X[L ... U], tem-se o algoritmo apresentado logo abaixo. Ao invés de computar do zero a maior soma terminando na posição 'I', a mesma é calculada utilizando a maior soma anteriormente armazenada para o intervalo [1 ... I – 1].

def algoritmo_linear(a):
    max_terminando_aqui = max_ate_agora = a[0]
    for x in a[1:]:
        max_terminando_aqui = max(x, max_terminando_aqui + x)
        max_ate_agora = max(max_ate_agora, max_terminando_aqui)
    return max_ate_agora

Algoritmo Linear (em Python)

A cada passo a variável max_terminando_aqui é incrementada com o valor do elemento da posição X[I]. Essencialmente, essa é a variável que vai acumulando as maiores somas das sublistas contíguas de tamanhos crescentes a cada passo da execução do algoritmo. Se a mesma atingir um valor negativo num dado momento, o algoritmo atribui o valor zero nesse caso.

O tempo de execução total é , conforme mencionado inicialmente, pois a lista de números é percorrida apenas uma vez do primeiro ao último elemento.

Retornando a sublista[editar | editar código-fonte]

O algoritmo linear ainda pode ser estendido de forma a retornar a sequência que contém a maior soma.

def subArray(a,size): 
  
    max_so_far = -maxsize - 1
    max_ending_here = 0
    start = 0
    end = 0
    s = 0
  
    for i in range(0,size): 
  
        max_ending_here += a[i] 
  
        if max_so_far < max_ending_here: 
            max_so_far = max_ending_here 
            start = s 
            end = i 
  
        if max_ending_here < 0: 
            max_ending_here = 0
            s = i+1
  
    print ("Maximum contiguous sum is %d"%(max_so_far)) 
    print ("Starting Index %d"%(start)) 
    print ("Ending Index %d"%(end))

Algoritmo Linear (em Phyton) que retorna a soma, a posição inicial e final.

Tempos de execução dos algoritmos[editar | editar código-fonte]

Abaixo, segue uma tabela com os tempos de execução dos algoritmos obtida através de testes realizados para entradas de diferentes tamanhos.


Entrada

Tempo de Resposta

Algoritmo Cúbico

Algoritmo Quadrático

Algoritmo Divisão e Conquista

Algoritmo Linear

n

O(n3)

O(n2)

O(n log n)

O(n)

100

3,10

microsegundos

3,10

microsegundos

3,20

microsegundos

3,10

microsegundos

101

133,00

microsegundos

39,00

microsegundos

73,40

microsegundos

9,40

microsegundos

102

37,00

milisegundos

2,63

milisegundos

3,08

milisegundos

93,00

microsegundos

103

32,30

segundos

243,00

milisegundos

247,18

milisegundos

930,00

microsegundos

104

6,53

horas

23,00

segundos

22,88

segundos

7,80

milisegundos

105

272,01

dias

51,67

minutos

20,95

minutos

78,00

milisegundos

106

745,18

anos

3,59

dias

29,55

horas

750,00

milisegundos

abc - medido

abc - calculado por extrapolação

 

Obs.: Os quatro algoritmos foram implementados na linguagem de programação Python. A execução foi realizada em uma máquina com processador Intel(R) Corel(TM)2 DUO CPU P8600 @ 2.40GHz 1,58 GHz, Memória RAM de 1,89 GB e Sistema Operacional: Microsoft Windows XP Professional Versão 2002 Service Pack 3.

Referências

Bentley, Jon (1984), "Programming pearls: algorithm design techniques", Communications of the ACM 27 (9): 865–873, DOI:10.1145/358234.381162.

Ligações externas[editar | editar código-fonte]