Kadane's Algorithm for Maximum Subarray Problem

Kadane's Algorithm for Maximum Subarray Problem

I just copied the below algorithm from wikipedia for reference. For more information, you can always go to

http://en.wikipedia.org/wiki/Maximum_subarray_problem
Kadane's Algorithm(array[1..n])

begin

(maxSum, maxStartIndex, maxEndIndex) := (-INFINITY, 0, 0)

currentMaxSum := 0

currentStartIndex := 1

for currentEndIndex := 1 to n do

currentMaxSum := currentMaxSum + array[currentEndIndex]

if currentMaxSum > maxSum then

(maxSum, maxStartIndex, maxEndIndex) := (currentMaxSum, currentStartIndex, currentEndIndex)

endif

if currentMaxSum < 0 then

currentMaxSum := 0

currentStartIndex := currentEndIndex + 1

endif

endfor

return (maxSum, maxStartIndex, maxEndIndex)

end

1 post / 0 new
For more complete information about compiler optimizations, see our Optimization Notice.