Suma máxima de subsecuencia:Marcos Weiss:

Question

En la parte resaltada a continuación, ¿cómo concluye Weiss que la matriz que comienza en un índice arbitrario "p" y termina en "j" nunca puede ser más grande que la matriz que comienza en "i" y termina en "p-1"?

Según su propio ejemplo (el bucle interno del algoritmo 2 que se muestra a continuación), esto es demostrablemente falso.

Sean i = 0 y j = 3.

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

Si p = 2, la suma de la subsecuencia de "p" a "j" es claramente mayor que "i" a "p-1".

Aún más preocupante es el Sr.Weiss parece sacar una suposición de la nada ("j es el primer índice que hace que la subsecuencia que comienza en el índice i se vuelva negativa") cuando nada de lo anterior podría implicar eso.De hecho, Weiss sólo menciona la "detección" de que la suma de la subsecuencia sea negativa entre el índice "i" y "j", pero nunca indica que la fuente de esto sólo podría ocurrir.¿De dónde viene esto?

¡Gracias por cualquier ayuda!

Answer 1

Creo que estás confundido acerca de qué algoritmo está describiendo.Su descripción no es para el algoritmo 2 sino para el algoritmo 4, donde un índice imaginario i en reintroducido.

Déjame escribir este algoritmo con este índice para que te quede claro:

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;

Ahora puedes ver que en este algoritmo, siempre que thisSum < 0, entonces j es de hecho el "primer índice que causa la subsecuencia que comienza en el índice i volverse negativo", y el resto del reclamo sigue.Tenga en cuenta en particular que el ejemplo que dio no puede ocurrir con este algoritmo (nunca tendrá i=0 y j=3 en ese caso).