Maximum Subsequence Sum : Mark Weiss:

Question

In the highlighted part below how is Weiss concluding that the array starting at an arbitrary index "p" and ending at "j" can never be larger than the array starting at "i" and ending at "p-1"?

By his own example (the inner loop of algorithm 2 shown below) this is demonstrably false.

Let i = 0, and j = 3.

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

If p = 2, the subsequence sum from "p" to "j" is clearly bigger than "i" to "p-1".

Even more concerning is Mr. Weiss seems to pull an assumption out of thin air ("j is the first index that causes the subsequence starting at index i to become negative") when nothing in the above could possibly imply that! Indeed, Weiss only mentions "detection" of the subsequence sum being negative between index "i" and "j", but never where the source of this could only occur. Where is this coming from?

Thanks for any help!

Answer 1

I think you are confused about which algorithm he is describing. His description isn't for algorithm 2 but for algorithm 4, where an imaginary index i in reintroduced.

Let me write this algorithm with this index to make it clear to you:

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;

Now you can see that in this algorithm, whenever thisSum < 0, then j is indeed the "first index that causes the subsequence starting at index i to become negative", and the rest of the claim follows. Notice in particular that the example you gave cannot occur with this algorithm (you will never have i=0 and j=3 in that case).