Maximale Folgesumme:Mark Weiss:

Question

Wie kommt Weiss im hervorgehobenen Teil unten zu dem Schluss, dass das Array, das bei einem beliebigen Index „p“ beginnt und bei „j“ endet, niemals größer sein kann als das Array, das bei „i“ beginnt und bei „p-1“ endet?

Anhand seines eigenen Beispiels (der unten gezeigten inneren Schleife von Algorithmus 2) ist dies nachweislich falsch.

Sei i = 0 und j = 3.

Sei a[ 0 ] = -14, a[ 1 ] = -4, a[ 2 ] = -2, a[ 3 ] = -1.

Wenn p = 2, ist die Teilsequenzsumme von „p“ bis „j“ deutlich größer als „i“ bis „p-1“.

Noch besorgniserregender ist Mr.Weiss scheint eine Annahme aus dem Nichts zu ziehen („j ist der erste Index, der bewirkt, dass die Teilfolge, die bei Index i beginnt, negativ wird“), obwohl nichts in dem oben Gesagten dies möglicherweise implizieren könnte!Tatsächlich erwähnt Weiss nur die „Erkennung“, dass die Teilsequenzsumme zwischen Index „i“ und „j“ negativ ist, jedoch nie dort, wo die Quelle dafür nur liegen könnte.Woher kommt das?

Vielen Dank für jede Hilfe!

Answer 1

Ich denke, Sie sind verwirrt darüber, welchen Algorithmus er beschreibt.Seine Beschreibung bezieht sich nicht auf Algorithmus 2, sondern auf Algorithmus 4, bei dem es sich um einen imaginären Index handelt i wieder eingeführt.

Lassen Sie mich diesen Algorithmus mit diesem Index schreiben, um es Ihnen klar zu machen:

maxSubSum(array a):
  maxSum = 0, thisSum = 0;
  i = 0;
  for j going from 0 to length(a)-1:
    thisSum += a[j];
    if thisSum > maxSum:
      maxSum = thisSum;
    else if thisSum < 0:
      i = j+1;
      thisSum = 0;
   return maxSum;

Jetzt können Sie das in diesem Algorithmus sehen, wann immer thisSum < 0 ist j ist in der Tat der „erste Index, der die Teilsequenz verursacht, die beim Index beginnt“. i negativ werden“, und der Rest der Behauptung folgt.Beachten Sie insbesondere, dass das von Ihnen angegebene Beispiel mit diesem Algorithmus nicht auftreten kann (das wird auch nie der Fall sein). i=0 Und j=3 In diesem Fall).