Soma máxima da subsequência:Marcos Weiss:

Question

Na parte destacada abaixo, como Weiss está concluindo que o array começando em um índice arbitrário "p" e terminando em "j" nunca pode ser maior do que o array começando em "i" e terminando em "p-1"?

Pelo seu próprio exemplo (o loop interno do algoritmo 2 mostrado abaixo), isso é comprovadamente falso.

Seja i = 0 e j = 3.

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

Se p = 2, a soma da subsequência de “p” a “j” é claramente maior que de “i” a “p-1”.

Ainda mais preocupante é o Sr.Weiss parece tirar uma suposição do nada ("j é o primeiro índice que faz com que a subsequência começando no índice i se torne negativa") quando nada acima poderia implicar isso!Na verdade, Weiss apenas menciona a "detecção" da soma da subsequência sendo negativa entre os índices "i" e "j", mas nunca onde a fonte disso poderia ocorrer.De onde vem isso?

Obrigado por qualquer ajuda!

Answer 1

Acho que você está confuso sobre qual algoritmo ele está descrevendo.Sua descrição não é para o algoritmo 2, mas para o algoritmo 4, onde um índice imaginário i em reintroduzido.

Deixe-me escrever este algoritmo com este índice para deixar claro para você:

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;

Agora você pode ver que neste algoritmo, sempre que thisSum < 0, então j é de fato o "primeiro índice que causa a subsequência começando no índice i para se tornar negativo", e o resto da afirmação segue.Observe em particular que o exemplo que você deu não pode ocorrer com este algoritmo (você nunca terá i=0 e j=3 nesse caso).