Максимальная сумма подпоследовательности:Марк Вайс:

Question

В выделенной части ниже, как Вайс приходит к выводу, что массив, начинающийся с произвольного индекса «p» и заканчивающийся «j», никогда не может быть больше, чем массив, начинающийся с «i» и заканчивающийся «p-1»?

На его собственном примере (внутренний цикл алгоритма 2, показанный ниже) это явно неверно.

Пусть i = 0 и j = 3.

Пусть a[ 0 ] = -14, a[ 1 ] = -4, a[ 2 ] = -2, a[ 3 ] = -1.

Если p = 2, сумма подпоследовательностей от «p» до «j» явно больше, чем от «i» до «p-1».

Еще больше беспокоит г-н.Кажется, Вайс вытащил предположение из воздуха («j — это первый индекс, который приводит к тому, что подпоследовательность, начинающаяся с индекса i, становится отрицательной»), хотя ничто из вышеизложенного не могло подразумевать это!Действительно, Вайс упоминает только «обнаружение» отрицательной суммы подпоследовательности между индексами «i» и «j», но никогда там, где источник этого мог только возникнуть.Откуда это взялось?

Спасибо за любую помощь!

Answer 1

Я думаю, вы не понимаете, какой алгоритм он описывает.Его описание относится не к алгоритму 2, а к алгоритму 4, где мнимый индекс i в вновь введенном виде.

Позвольте мне написать этот алгоритм с этим индексом, чтобы вам было понятнее:

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;

Теперь вы можете видеть, что в этом алгоритме всякий раз, когда thisSum < 0, тогда j действительно является «первым индексом, который вызывает подпоследовательность, начинающуюся с индекса i стать отрицательным», и далее следует остальная часть утверждения.Обратите внимание, в частности, что пример, который вы привели, не может произойти с этим алгоритмом (у вас никогда не будет i=0 и j=3 в таком случае).