Max sum of a subarray of integers

This is the classical kadane's algorithm and it's always a pearl to study.  A couple of key observations: (1) the empty subarray has sum 0, and this is the minimum. (2) We can maintain a running sum and when we go negative we start again with the empty subarray

So

max_so_far = max_ending_here  = 0;
for (i  = 0; i < A.size(); i++)
{
   max_so_far = max (0, max_so_far+A[i]);  /// if we get negative, consider the empty string
   max_ending_here = max (max_so_far, max_ending_here);
}