Maximum Subsequence Sum : Mark Weiss:
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 &gt; maxSum:
      maxSum = thisSum;
    else if thisSum &lt; 0:
      i = j+1;
      thisSum = 0;
   return maxSum;


Now you can see that in this algorithm, whenever thisSum &lt; 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).