Maximum subarray problem: Difference between revisions

Revision as of 06:39, 28 November 2010

Revision as of 07:10, 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 code,algorithm. expressedThe herealgorithm inkeeps [[Pythontrack of the tentative maximum subsequence in (programmingmaxSum, languagemaxStartIndex, maxEndIndex)|Python]]:. It accumulates a partial sum in currentMaxSum and updates the optimal range when this partial sum becomes larger than maxSum.

<pre>

<source lang="python">

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

def max_subarray(A):

begin

max_so_far = max_ending_here = 0

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

for x in A:

currentMaxSum := 0

max_ending_here = max(0, max_ending_here + x)

currentStartIndex := 1

max_so_far = max(max_so_far, max_ending_here)

for currentEndIndex := 1 to n do

return max_so_far

currentMaxSum := currentMaxSum + array[currentEndIndex]

</source>

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

</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]].