Maximum subarray problem: Difference between revisions

Revision as of 23:18, 23 February 2025

Latest revision as of 15:17, 26 February 2025

(2 intermediate revisions by 2 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.

Line 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.

}}