## 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)

/* 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

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

## No comments:

## Post a Comment