Algoritmi e Strutture Dati

Conquer Maximum Sum Subarray with Divide & Conquer Algorithm

Esistono molti modi per trovare il sottoarray con la somma massima all’interno di n interi. Uno dei metodi per risolvere il problema consiste nell’utilizzare un algoritmo di tipo divide & conquer (divide et impera). Per affrontare il problema, si suddivide ricorsivamente l’array in due parti, si individua il sottoarray di somma massima nella parte sinistra, nella parte destra e nella parte che attraversa il punto centrale, e si calcola la soluzione per l’array attuale a partire da questi risultati.
Quindi, il pseudocodice per l’algoritmo potrebbe essere:
def max_subarray(a):
    # Casi base
    if len(a) == 0:
        return float('-inf'), float('-inf'), float('-inf')
    if len(a) == 1:
        return a[0], a[0], a[0]

    # Divide (recupera le risposte per la parte sinistra e quella destra)
    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:])

    # Ottieni 3 valori e restituisci maxi-prefisso, maxi-suffisso e somma massima totale
    return conquer(ll, lmax, lr, lsum, rl, rmax, rr, rsum)
In questo problema, ti viene richiesto di implementare la parte conquer, dove, dati 8 numeri, dovrai trovare correttamente 3 valori che rappresentino la migliore somma di prefisso, la somma migliore che attraversa il punto centrale e la migliore somma di suffisso. Gli 8 numeri forniti sono:
  1. La migliore somma di prefisso per il sottoarray sinistro
  1. La somma massima del sottoarray sinistro
  1. La migliore somma di suffisso per il sottoarray sinistro
  1. La somma di tutti i numeri nel sottoarray sinistro
  1. La migliore somma di prefisso per il sottoarray destro
  1. La somma massima del sottoarray destro
  1. La migliore somma di suffisso per il sottoarray destro
  1. La somma di tutti i numeri nel sottoarray destro

Input

L’unica riga di input contiene 8 interi nell’ordine sopra descritto. Tutti gli interi non superano in valore assoluto.

Output

Il programma deve stampare 3 numeri: la migliore somma di prefisso, la migliore somma che attraversa il punto centrale e la migliore somma di suffisso.

Examples

Input
Output
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