Algorithmen und Datenstrukturen

Das Maximum-Sum-Subarray mithilfe des Divide-&-Conquer-Algorithmus meistern

Es gibt verschiedene Methoden, um das Maximum-Sum-Subarray einer Folge von n Ganzzahlen zu finden. Eine dieser Methoden basiert auf dem Divide-&-Conquer-Ansatz. Dabei wird das Array rekursiv in zwei Teile aufgeteilt: Zunächst ermitteln wir das Maximum-Sum-Subarray für den linken und für den rechten Teil sowie für den überlappenden Bereich, der den Mittelpunkt überschreitet. Aus diesen drei Werten ergibt sich dann die beste Lösung für das aktuelle (in diesem Fall, das gesamte) Array.
Untenstehend sehen Sie den Pseudocode des Algorithmus:
def max_subarray(a):
    # Basisfälle
    if len(a) == 0:
        return float('-inf'), float('-inf'), float('-inf')
    if len(a) == 1:
        return a[0], a[0], a[0]

    # Aufteilen (Ergebnisse für linken und rechten Teil holen)
    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:])

    # Ermitteln Sie 3 Werte und geben Sie das maximale Präfix, das maximale Suffix sowie die Gesamt-Maximalsumme zurück
    return conquer(ll, lmax, lr, lsum, rl, rmax, rr, rsum)
In dieser Aufgabe sollen Sie den conquer-Teil implementieren. Ihnen werden dabei 8 Zahlen übergeben, aus denen Sie die folgenden 3 Werte bestimmen sollen: den besten Präfix-Summenwert, die beste Summe über den Mittelpunkt hinweg und den besten Suffix-Summenwert. Die 8 übergebenen Zahlen entsprechen in dieser Reihenfolge:
  1. Der beste Präfix-Summenwert des linken Teilarrays
  1. Die maximale Summe des linken Teilarrays
  1. Der beste Suffix-Summenwert des linken Teilarrays
  1. Die Summe aller Zahlen im linken Teilarray
  1. Der beste Präfix-Summenwert des rechten Teilarrays
  1. Die maximale Summe des rechten Teilarrays
  1. Der beste Suffix-Summenwert des rechten Teilarrays
  1. Die Summe aller Zahlen im rechten Teilarray

Eingabe

Die Eingabe besteht aus genau einer Zeile mit 8 Ganzzahlen (in der oben genannten Reihenfolge). Alle Ganzzahlen haben Beträge von höchstens .

Ausgabe

Das Programm soll 3 Zahlen ausgeben: den besten Präfix-Summenwert, die beste Summe über den Mittelpunkt hinweg und den besten Suffix-Summenwert.

Beispiele

Eingabe
Ausgabe
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