Máximo valor da soma de uma subsequência contínua

Question

Considere o problema de encontrar a maior soma de uma sequência contínua de elementos de uma lista de inteiros. Por exemplo, a sequência de valores -2, 1, -3,
4, -1, 2, 1, -5, 4 tem a maior soma igual a 6, que nesse caso é encontrada para a sequência
contínua 4, -1, 2, 1.

Resolva esse problema usando divisão e conquista, apresente um pseudo-código e calcule a complexidade computacional dessa
solução.

Dica:

1) Divida a lista em 2 partes.

2) Retorne o máximo de um dos três:

(i) Máxima soma
da lista da esquerda (chamada recursiva);

(ii) Máxima soma da lista da direita (chamada recursiva);

(iii) Máxima soma da lista que cruza o ponto do meio entre as duas lista (que pode ser feito com custo linear)

Answer 1

def maior_soma(lista):
    n = len(lista)
    if n == 0:
        return 0
    if n == 1:
        return max(lista[0], 0)

    lista_esquerda = lista[:n // 2]
    lista_direita = lista[n // 2:]

    maximo_esquerda = maior_soma(lista_esquerda)
    maximo_direita = maior_soma(lista_direita)

    m_esq, soma_esq = 0, 0
    for x in lista_esquerda[::-1]:
        soma_esq += x
        m_esq = max(m_esq, soma_esq)

    m_dir, soma_dir = 0, 0
    for x in lista_direita:
        soma_dir += x
        m_dir = max(m_dir, soma_dir)

    maximo_cruza = m_esq + m_dir

    return max(maximo_esquerda, maximo_direita, maximo_cruza)


x = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maior_soma(x))