最大子序列和：马克·韦斯：

Question

在下面突出显示的部分中，Weiss 如何得出从任意索引“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”。

更让人关心的是先生。Weiss 似乎凭空提出了一个假设（“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 在这种情况下）。