Maximum subarray problem: Difference between revisions

Revision as of 03:17, 30 March 2008

Revision as of 03:25, 30 March 2008

Line 1:

In [[computer science]], the '''maximum subarray problem''' for a given one-dimensional [[array]] of numbers is to find the contiguous subarray with maximum sum. The problem was first posed by [[Ulf Grenander]] of [[Brown University]] in 1977, as a simplified model for [[maximum likelihood]] estimation of patterns in digitized images. A [[linear time]] [[algorithm]] to solve it was found soon afterwards by [[Jay Kadane]] of [[Carnegie-Mellon University]], and first published by {{harvtxt|Bentley|1984}}.

==Example==

The 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, expressed here in [[Python (programming language)|Python]]:

Suppose that array ''A'' consists of the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4. Then the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

==Kadane's algorithm==

TheKadane'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, expressed here in [[Python (programming language)|Python]]:

<source lang="python">