Algoritmos e Estruturas de Dados

Domine o Subarray de Soma Máxima com o Algoritmo de Dividir & Conquistar

Existem muitas formas de encontrar a subarray de soma máxima em um conjunto de n inteiros. Uma dessas maneiras utiliza o algoritmo de dividir & conquistar. Para resolver esse problema, é preciso dividir o array recursivamente em 2 partes, identificar a subarray de soma máxima na parte esquerda, na parte direita e na parte que cruza o ponto médio em cada uma dessas divisões, e então combinar esses resultados para obter a resposta do array original.
O pseudocódigo do algoritmo pode ser o seguinte:
def max_subarray(a):
    # Casos base
    if len(a) == 0:
        return float('-inf'), float('-inf'), float('-inf')
    if len(a) == 1:
        return a[0], a[0], a[0]

    # Dividir (obter as respostas para as partes esquerda e direita)
    ll, lmax, lr = max_subarray(a[:len(a) // 2])
    rl, rmax, rr = max_subarray(a[len(a) // 2:])
    lsum = sum(a[:len(a) // 2])
    rsum = sum(a[len(a) // 2:])

    # Obter 3 valores e retornar o prefixo máximo, o sufixo máximo e a soma máxima total
    return conquer(ll, lmax, lr, lsum, rl, rmax, rr, rsum)
Neste problema, você é convidado a implementar a parte conquer, na qual, dados 8 números, deverá identificar corretamente os 3 valores que representam o melhor prefixo (prefix-sum), a melhor soma que cruza o ponto médio e o melhor sufixo (suffix-sum). Os 8 valores que são fornecidos são:
  1. O melhor prefix sum do subarray esquerdo
  1. A soma máxima do subarray esquerdo
  1. O melhor suffix sum do subarray esquerdo
  1. A soma total dos elementos do subarray esquerdo
  1. O melhor prefix sum do subarray direito
  1. A soma máxima do subarray direito
  1. O melhor suffix sum do subarray direito
  1. A soma total dos elementos do subarray direito

Entrada

A única linha da entrada contém 8 inteiros na ordem descrita acima. Cada inteiro não excede em valor absoluto.

Saída

O programa deve imprimir 3 números - o melhor prefix sum, a melhor soma que cruza o ponto médio e o melhor suffix sum.

Exemplos

Entrada
Saída
7 13 9 6 7 9 3 -2
13 16 7
7 13 9 6 5 25 3 1
11 25 10
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue