Maximum subarray problem: Difference between revisions

Revision as of 06:22, 28 November 2010

Revision as of 06:39, 28 November 2010

Line 4:

==Kadane's algorithm==

Kadane's algorithm consists of a scan through the array values, computing at each position the maximum subarray ending at that position. This subarray is either empty (in which case [[empty sum|its sum is zero]]) or consists of one more element than the maximum subarray ending at the previous position. Thus, the problem can be solved with the following algorithm.code, Theexpressed algorithmhere keepsin track of the tentative maximum subsequence in[[Python (maxSum,programming maxStartIndex, maxEndIndexlanguage). It accumulates a partial sum in currentMaxSum and updates the optimal range when this partial sum becomes larger than maxSum.|Python]]:

<source lang="python">

<pre>

def max_subarray(A):

Kadane's Algorithm(array[1..n])

max_so_far = max_ending_here = 0

begin

for x in A:

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

max_ending_here = max(0, max_ending_here + x)

currentMaxSum := 0

max_so_far = max(max_so_far, max_ending_here)

currentStartIndex := 1

return max_so_far

for currentEndIndex := 1 to n do

</source>

currentMaxSum := currentMaxSum + array[currentEndIndex]

if currentMaxSum > maxSum then

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

endif

if currentMax < 0 then

currentMax := 0

currentStartIndex := currentEndIndex + 1

endif

endfor

return (maxSum, maxStartIndex, maxEndIndex)

end

</pre>

Because of the way this algorithm uses optimal substructures (the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem, the maximum subarray ending at the previous position) this algorithm can be viewed as a simple example of [[dynamic programming]].