Maximum subarray problem: Difference between revisions

Revision as of 01:37, 16 March 2010

Revision as of 01:43, 16 March 2010

Line 1:

In [[computer science]], the '''maximum subarray problem''' is the task of finding the contiguous subarray within a one-dimensional [[array]] of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

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]] was found soon afterwards by [[Jay Kadane]] of [[Carnegie-Mellon University]] ({{harvtxtharv|Bentley|1984}}).

==Kadane's algorithm==