Find the sub-array with the largest sum. [ALGORITHM PUZZLE Technical]

Assuming neither the array nor sub-array can be empty, there are two possibilities.

1. Either all values in the array are negative, in which case the sub-array with the largest sum is the 1-element sub-array containing the maximum value, or
2. There are non-negative values in the array and the sub-array is bounded by negative value(s) and/or the maximum/minimum indexes.

The algorithm is to iterate through the array calculating the sum.  Whenever the sum drops below zero, reset the sum to zero and reset the low index.  Whenever the sum exceeds the maximum sum, record the new maximum and the sub-array indexes for the maximum.

Given an array a of size s:

msum = smallest negative integer
mlow = -1
mhigh = -1
low = -1
sum = 0
for i = 0; i < s; i = i + 1 {
  if a[i] < 0 {
    if a[i] > msum {
      msum = a[i]
      mlow = mhigh = i
    }
    else {
      sum += a[i]
      if sum < 0 {
        sum = 0
        low = -1
      }
    }
  }
  else {
    if low == -1 {
      low = i
    }
    sum += a[i]
    if sum > msum {
      mlow = low
      msum = sum
      mhigh = i
    }
  }
}
// sub-array is a[mlow..mhigh] with a sum of msum