Maximum subarray problem: Difference between revisions

Revision as of 22:13, 28 June 2024

Latest revision as of 15:17, 26 February 2025

(9 intermediate revisions by 7 users not shown)

Line 20:

The maximum subarray problem was proposed by [[Ulf Grenander]] in 1977 as a simplified model for [[maximum likelihood estimation]] of patterns in digitized images.{{sfn|Bentley|1984|p=868-869}}

Grenander was looking to find a rectangular subarray with maximum sum, in a two-dimensional array of real numbers. A brute-force algorithm for the two-dimensional problem runs in ''O''(''n''⁶) time; because this was prohibitively slow, Grenander proposed the one-dimensional problem to gain insight into its structure. Grenander derived an algorithm that solves the one-dimensional problem in ''O''(''n''²) time, using [[prefix sum]]{{NoteTag

|By using a precomputed table of cumulative sums <math>S[k] = \sum_{x=1}^k A[x]</math> to compute the subarray sum <math>\sum_{x=i}^j A[x] = S[j] - S[i-1]</math> in constant time<!--sentence fragment-->

}}, improving the brute force running time of ''O''(''n''³). When [[Michael Shamos]] heard about the problem, he overnight devised an ''O''(''n'' log ''n'') [[divide-and-conquer algorithm]] for it.

}}

improving the brute force running time of ''O''(''n''³). When [[Michael Shamos]] heard about the problem, he overnight devised an ''O''(''n'' log ''n'') [[divide-and-conquer algorithm]] for it.

Soon after, Shamos described the one-dimensional problem and its history at a [[Carnegie Mellon University]] seminar attended by [[Jay Kadane]], who designed within a minute an ''O''(''n'')-time algorithm,{{sfn|Bentley|1984|p=868-869}}{{sfn|Bentley|1989|p=76-77}}{{sfn|Gries|1982|p=211}} which is as fast as possible.<ref group=note>since every algorithm must at least scan the array once which already takes ''O''(''n'') time</ref> In 1982, [[David Gries]] obtained the same ''O''(''n'')-time algorithm by applying [[Edsger W. Dijkstra |Dijkstra]]'s "standard strategy";{{sfn|Gries|1982|p=209-211}} in 1989, [[Richard Bird (computer scientist)|Richard Bird]] derived it by purely algebraic manipulation of the brute-force algorithm using the [[Bird–Meertens formalism]].{{sfn|Bird|1989|loc=Sect.8, p.126}}

Line 58 ⟶ 57:

def max_subarray(numbers):

"""Find the largest sum of any contiguous subarray."""

best_sum = float('- infinityinf')

current_sum = 0

for x in numbers:

Line 70 ⟶ 69:

The algorithm can be adapted to the case which allows empty subarrays or to keep track of the starting and ending indices of the maximum subarray.

This algorithm calculates the maximum subarray ending at each position from the maximum subarray ending at the previous position, so it can be viewed as a trivial case of [[dynamic programming]].

===Empty subarrays admitted===

Line 78 ⟶ 77:

| [[File:Kadane run −2,1,−3,4,−1,2,1,−5,4.gif|thumb|500px|Execution of Kadane's algorithm on the [[#top|above]] example array. ''{{color|#0000c0|Blue}}:'' subarray with largest sum ending at ''i''; ''{{color|#00c000|green}}:'' subarray with largest sum encountered so far; a lower case letter indicates an empty array; variable ''i'' is left implicit in Python code.]]

|}

Kadane's original algorithm, solvesas originally published, is for solving the problem variant whenwhich allows empty subarrays are admitted.{{sfn|Bentley|1989|p=74}}{{sfn|Gries|1982|p=211}}

ThisIn such variant, the willanswer returnis 0 ifwhen the input contains no positive elements (including when the input is empty).

ItThe variant is obtained bywith two changes in code: in line 3, <code>best_sum</code> should be initialized to 0 to account for the empty subarray <math>A[0 \ldots -1]</math>

<syntaxhighlight lang="python" line start="3">

best_sum = 0;

</syntaxhighlight>

and line 6 in the for loop <code>current_sum</code> should be updated asto <code>max(0, current_sum + x)</code>.{{NoteTag

|While {{harvtxt|Bentley|1989}} does not mention this difference, using <code>x</code> instead of <code>0</code> in the [[#No empty subarrays admitted|above]] version without empty subarrays achieves maintaining its loop invariant <code>current_sum</code><math>=\max_{i \in \{ 1, ..., j-1 \}} A[i]+...+A[j-1]</math> at the beginning of the <math>j</math>th step.

}}

Line 116 ⟶ 115:

{{NoteFoot|30em}}

==ReferencesNotes==

{{Reflist}}

==References==

*{{citation

| last1 = Alves | first1 = Carlos E. R.

Line 132 ⟶ 133:

| title = Recent Advances in Parallel Virtual Machine and Message Passing Interface, 11th European PVM/MPI Users' Group Meeting, Budapest, Hungary, September 19-22, 2004, Proceedings

| volume = 3241

| year = 2004}}| isbn = 978-3-540-23163-9

}}

*{{citation

| last1 = Backurs

Line 148 ⟶ 150:

| pages = 81:1–81:13

| doi = 10.4230/LIPIcs.ICALP.2016.81

| doi-access = free

| s2cid = 12720136

}}

Line 211 ⟶ 214:

}}

*{{citation

| url=http://comjnl.oxfordjournals.org/content/32/2/122.full.pdf

| first=Richard S.

| last= Bird

Line 222 ⟶ 224:

| year=1989

| doi=10.1093/comjnl/32.2.122

}}

}}{{dead link|date=May 2021|bot=medic}}{{cbignore|bot=medic}}

*{{citation

| first1 = Gerth Stølting | last1 = Brodal

Line 283 ⟶ 285:

| pages = 446–452

| doi =

| isbn = 978-0-89871-410-4

| access-date = November 17, 2018

}}

Line 296 ⟶ 299:

| title = Maximum subarray algorithms for use in astronomical imaging

| volume = 22

| year = 2013}}| bibcode = 2013JEI....22d3011W

}}

== External links ==

Line 309 ⟶ 313:

[[Category:Optimization algorithms and methods]]

[[Category:Dynamic programming]]

[[Category:Polynomial-time problems]]

[[Category:Articles with example Python (programming language) code]]