Somma massima della sottosequenza:Mark Weiss:

Question

Nella parte evidenziata di seguito, come fa Weiss a concludere che l'array che inizia con un indice arbitrario "p" e termina con "j" non può mai essere più grande dell'array che inizia con "i" e termina con "p-1"?

Secondo il suo esempio (il ciclo interno dell'algoritmo 2 mostrato di seguito) questo è palesemente falso.

Sia i = 0 e j = 3.

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

Se p = 2, la somma della sottosuccessione da "p" a "j" è chiaramente maggiore di quella da "i" a "p-1".

Ancora più preoccupante è Mr.Weiss sembra tirare fuori un'ipotesi dal nulla ("j è il primo indice che fa sì che la sottosequenza che inizia dall'indice i diventi negativa") quando nulla di quanto sopra potrebbe implicarlo!In effetti Weiss menziona solo il "rilevamento" della somma successiva negativa tra l'indice "i" e "j", ma mai dove l'origine di ciò potrebbe solo verificarsi.Da dove viene questo?

Grazie per qualsiasi aiuto!

Answer 1

Penso che tu sia confuso su quale algoritmo sta descrivendo.La sua descrizione non è per l'algoritmo 2 ma per l'algoritmo 4, dove un indice immaginario i in reintrodotto.

Lasciami scrivere questo algoritmo con questo indice per renderlo chiaro:

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;

Ora puoi vederlo in questo algoritmo, ogni volta che thisSum < 0, allora j è infatti il ​​"primo indice che provoca la sottosequenza a partire da indice i diventare negativo", e il resto della tesi segue.Nota in particolare che l'esempio che hai fornito non può verificarsi con questo algoritmo (non lo avrai mai i=0 E j=3 in quel caso).