Maximum subarray problem: Difference between revisions

Revision as of 07:01, 17 December 2024

Latest revision as of 15:17, 26 February 2025

(4 intermediate revisions by 3 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 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 314 ⟶ 313:

[[Category:Optimization algorithms and methods]]

[[Category:Dynamic programming]]

[[Category:Polynomial-time problems]]

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