|
In [[computer science]], the '''maximum subarray problem''' for a given one-dimensional [[array]] of numbers is the computational task of finding the contiguous subarray withwithin maximuma sum. The problem was first posed byone-dimensional [[Ulf Grenanderarray]] of [[Brownnumbers University]]which inhas 1977,the aslargest asum. simplifiedFor modelexample, for [[maximumthe likelihood]] estimationsequence of patternsvalues in−2, digitized1, images.−3, A4, [[linear−1, time]]2, [[algorithm]]1, to−5, solve4; itthe wascontiguous foundsubarray soonwith afterwardsthe bylargest [[Jaysum Kadane]]is of4, [[Carnegie-Mellon−1, University]]2, and1, firstwith publishedsum by {{harvtxt|Bentley|1984}}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]] ({{harvtxt|Bentley|1984}}).
==Example==
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==
|
