Maximum subarray problem: Difference between revisions

Revision as of 11:45, 18 March 2011

Revision as of 14:47, 18 March 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. The algorithm keeps track of the tentative maximum subsequence in (maxSum, maxStartIndex, maxEndIndex). It accumulates a partial sum in currentMaxSum and updates the optimal range when this partial sum becomes larger than maxSum.

<pre>

Line 27:

end

</pre>

It should be noted that the algorithm as presented does not work for arrays consisting of all negative numbers and returns 0 in this case (see comparison currentMaxSum < 0). To cater for such a case a simple pre-scan for all negative numbers can be performed and the index of the least negative number returned.

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