Content deleted Content added
m [r2.5.2] robot Adding: fa:مساله زیر آرایه بیشینه |
m Disambiguated: array → array data structure using Dab solver |
||
Line 1:
In [[computer science]], the '''maximum subarray problem''' is the task of finding the contiguous subarray within a one-dimensional [[array data structure|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]] {{harv|Bentley|1984}}.
| |||