Maximum subarray problem: Difference between revisions

Revision as of 09:47, 13 May 2011

Revision as of 14:29, 13 May 2011

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) := (0, 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 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]].

Line 56 ⟶ 43:

* [http://www.algorithmist.com/index.php/Kadane's_Algorithm www.algorithmist.com]

* [http://alexeigor.wikidot.com/kadane alexeigor.wikidot.com]

* [http://www.cs.waikato.ac.nz/Teaching/COMP317B/Week_1/AlgorithmDesignTechniques.pdf Algorithm Design Techniques]

[[Category:Optimization algorithms]]

[[Category:Dynamic programming]]

[[Category:Articles with example Python code]]

[[fa:مسئله زیرآرایه بیشینه]]