Maximum subarray problem: Difference between revisions

Revision as of 06:18, 28 November 2010

Revision as of 06:22, 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:. 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>