Wie findet man die größte Summe aufeinanderfolgender Glieder der Folge von n positiven und negativen Zahlen?

Question

Ich versuchte dieses Problem zu lösen, indem ich mich in zwei Hälften teilte und die größte Summe in jedem fand. Ich habe MegaSort benutzt. Aber ich bin fest, wie ich die größte Summe von jeder rekursiven Funktion aufzeichnen und zurückgeben kann. Zum Beispiel

[1, -3, 4, -7, 8] -> die größte Summe sollte 8. (Summe selbst) seine

[5,5, -3,6, - 10] -> die größte Summe sollte 5 + 5 + (-3) + 6 = 13

[3, -9, 10, 5] -> die größte Summe 10 + 5 = 15

def find_max(seq): 
    if len(seq) == 1: 
     if(seq[0] > sum): 
      sum = seq[0] 
     return seq 
    else: 
     mid = len(seq)//2 
     left = [:seq] 
     right = [seq:] 
     find_max(left) 
     find_max(right) 

Answer 1

Ich bin nicht sicher, dass diese Antwort hilfreich sein wird, da ich verstehe, dass Ihre Frage nicht den Algorithmus selbst betrifft, sondern die Implementierung mit Python (und ich kenne Python nicht). Aber es gibt einen anderen Algorithmus, den Sie verwenden könnten, den Sie ohne Hilfe implementieren können. Beachten Sie, dass dieser Algorithmus nur die Summe berechnet, nicht die Reihenfolge, die diese Summe angibt (soweit ich das verstehe, ist das was Sie wollen). Hier ist die C-ähnliche Pseudocode-Lösung:

int findMax(sequence, length) { 

    int maxSumStartingAt[length]; 
    maxSumStartingAt[length - 1] = sequence[length-1]; 

    for(int i=length-2; i >= 0; i--) { 
     int tempSum = sequence[i] + maxSumStartingAt[i+1]; 
     if (sequence[i] > tempSum) { 
      maxSumStartingAt[i] = sequence[i]; 
     } else { 
      maxSumStartingAt[i] = tempSum; 
     } 
    } 

    int maxSum = maxSumStartingAt[0]; 
    for(int i = 1; i < length; i++) { 
     if (maxSum < maxSumStartingAt[i]) { 
      maxSum = maxSumStartingAt[i]; 
     } 
    } 

    return maxSum; 
} 

Jetzt erkläre ich Ihnen, wie diese Lösung funktioniert.

1) Da die Teilfolge, die die größte Summe ergibt, bei einem Index i beginnen muss, besteht die Idee darin, für jeden Index i die größte Summe aufeinanderfolgender Elemente beginnend bei i zu berechnen. Das Ergebnis ist das Maximum zwischen diesen Summen.

2) Nun, wenn Ihnen jemand gesagt hat, dass die Teilfolge der Elemente, die die größte Summe ergeben, bei Index i beginnt und dass die größte Summe aufeinanderfolgender Elemente für die Teilsequenz beginnend bei Index i + 1 x ist, wie können Sie Berechnen Sie die gewünschte Summe? Es wäre einfach das Maximum zwischen

sequence[i] 

und

sequence[i] + x 

Wir können anhand dieser Informationen die größte Summe ab Index zu berechnen, i für jeden Index i: Wir beginnen von dem letzten Element der Sequenz aka,

sequence[length-1] 

wenn wir die Indizierung von 0 beginnen Was ist die größte Summe an diesem Index begonnen, die ich nennen würde maxSumStartingAt [length-1]? kann es sein, keine andere als

sequence[length - 1] 

selbst da dies eine 1-Element-Sequenz. Und was ist die größte Summe ab Indexlänge - 2? Es ist das Maximum zwischen

sequence[length-2] 

und

sequence[length-2] + maxSumStartingAt[length-1] 

Und was die größte Summe an Indexlänge wird gerade - 3?Wieder ist es das Maximum zwischen

sequence[length-3] 

und

sequence[length-3] + maxSumStartingAt[length-2] 

Wir haben diese Formel, um jeden Index der Sequenz anwenden können, und schließlich kommen wir zum Index 0 und wir haben die größte Summe an den generischen Anfang Index ich für jeden Index. Dies ist genau das, was die erste for-Schleife in der Lösung tut. An diesem Punkt müssen wir nur das Maximum zwischen allen berechneten Summen finden (das ist es, was die zweite for-Schleife in der Lösung tut). Dieses Maximum ist das Ergebnis.

Ein Hinweis zu Ihrer Lösung. Da ich Python nicht kenne, kann ich den von Ihnen geposteten Code nicht beurteilen, wenn er genau das tut, was Sie in der Frage angegeben haben (dh die Sequenz in zwei Hälften teilen und die größte Summe für jede Hälfte berechnen, dann das Maximum zurückgeben) zwischen diesen beiden Werten) funktioniert es nicht, da es nicht den Fall abdeckt, in dem die größte Summe von einer Sequenz geliefert wird, die sich über die zwei Hälften erstreckt.

Answer 2

def largestSum(arr): 
    curr = arr[0] 
    lsum = arr[0] 

    if len(arr) <= 1: 
    return arr 

    for i in range(1, len(arr)): 
    curr = max(arr[i], curr + arr[i]) 

    if curr > lsum: 
     lsum = curr 
    return lsum 

largestSum([-2,3,2,-1])