Maximum-sum contiguous subvector

Question

Given an array A[1..n] of n real numbers, write programming code which implements an O(n)-time algorithm for finding the maximum-sum contiguous subvector. For example, in the array
{11, -21, 39, 6, -33, 38, 77, -73, -3, 64}
the maximum sum (122) is obtained by summing the third through seventh elements; your code should print 122 3 7.

Solution

Maximum sum in any contiguous subvector
/* Precondition: x[1..n] is an array of floating-point (real) numbers. */
procedure MaxSumContigVector (x[1..n]: float)

// Returns the maximum sum of a continuous subarray drawn from x.

MaxSoFar := 0.0

MaxEndingHere := 0

i := 1

while i ≠ n + 1 do

MaxEndingHere := max(0.0, MaxEndingHere + x[i])

MaxSoFar := max(MaxSoFar, MaxEndingHere)

i := i + 1

end

return MaxSoFar

source:
http://www.cse.sc.edu/~mgv/csce350sp04/lectureNotes/maxsumcontigvector.html