Maximum subarray problem: Difference between revisions

Revision as of 15:17, 13 September 2023

Revision as of 15:19, 13 September 2023

Line 36:

In [[computer vision]], maximum-subarray algorithms are used on bitmap images to detect the brightest area in an image.

==Kadane's algorithm==

===EmptyNo empty subarrays admitted===

{| align="right" class="wikitable collapsible collapsed"

[[Joseph Born Kadane|Kadane's]] original algorithm solves the problem version when empty subarrays are admitted. It scans the given array <math>A[1\ldots n]</math> from left to right.

! Example run

|-

| [[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.]]

|}

[[Joseph Born Kadane|Kadane's]] original algorithm solves the problem version when empty subarrays are admitted. It scans the given array <math>A[1\ldots n]</math> from left to right.

In the <math>j</math>th step, it computes the subarray with the largest sum ending at <math>j</math>; this sum is maintained in variable <code>current_sum</code>.{{NoteTag

|named <code>MaxEndingHere</code> in {{harvtxt|Bentley|1989}}, and <code>c</code> in {{harvtxt|Gries|1982}}

Line 52 ⟶ 48:

and easily obtained as the maximum of all values of <code>current_sum</code> seen so far, cf. line 7 of the algorithm.

As a [[loop invariant]], in the <math>j</math>th step, the old value of <code>current_sum</code> holds the maximum over all <math>i \in \{ 1,\ldots, j-1 \}</math> of the sum <math>A[i]+\cdots+A[j-1]</math>.{{NoteTag

|This sum is <math>0</math> when <math>i=j</math>, corresponding to the empty subarray <math>A[j\ldots j-1]</math>.

}}

Therefore, <code>current_sum</code><math>+A[j]</math>{{NoteTag|

In the Python code below, <math>A[j]</math> is expressed as <code>x</code>, with the index <math>j</math> left implicit.

}}

is the maximum over all <math>i \in \{ 1,\ldots, j-1 \}</math> of the sum <math>A[i]+\cdots+A[j]</math>. To extend the latter maximum to cover also the case <math>i=j+1</math>, it is sufficient to consider also the emptysingleton subarray <math>A[j+1 \; \ldots \; j]</math>. This is done in line 6 by assigning <math>\max(0A[j],</math><code>current_sum</code><math>+A[j])</math> as the new value of <code>current_sum</code>, which after that holds the maximum over all <math>i \in \{ 1, \ldots, j+1 \}</math> of the sum <math>A[i]+\cdots+A[j]</math>.

Thus, the problem can be solved with the following code,{{sfn|Bentley|1989|p=74}}{{sfn78,171|Gries|1982|pps=211}}. expressedBentley, belowlike inGries, [[Pythonfirst (programmingintroduces language)|Python]].the Thisvariant versionadmitting ofempty thesubarrays, algorithmsee will[[#Empty returnsubarrays 0admitted|below]], ifand describes only the inputchanges.}} containsexpressed noin positive elements[[Python (includingprogramming when the input is emptylanguage)|Python]].

<syntaxhighlight lang="python" line>

def max_subarray(numbers):

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

best_sum = 0- infinity

current_sum = 0

for x in numbers:

current_sum = max(0x, current_sum + x)

best_sum = max(best_sum, current_sum)

return best_sum

</syntaxhighlight>

In that case, ifIf the input contains no positive element, the returned value is that of the largest element (i.e., the value closest to 0), or negative infinity if the input was empty. For correctness, an exception should be raised when the input array is empty, since an empty array has no maximum nonempty subarray. If the array is non-emptynonempty, its first element cancould be used in place of negative infinity, if needed to avoid mixing numeric and non-numeric values.

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

The algorithm can be adapted to the case which disallowsallows 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]].

===No emptyEmpty subarrays admitted===

{| align="right" class="wikitable collapsible collapsed"

For the variant of the problem which disallows empty subarrays, <code>best_sum</code> should be initialized to negative infinity instead{{sfn|Bentley|1989|p=78,171}}

! Example run

|-

| [[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 solves the problem variant when empty subarrays are admitted.{{sfn|Bentley|1989|p=74}}{{sfn|Gries|1982|p=211}}

This variant will return 0 if the input contains no positive elements (including when the input is empty).

It is obtained by 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 = - infinity0;

</syntaxhighlight>

and alsoline 6 in the for loop <code>current_sum</code> should be updated as <code>max(x0, current_sum + x)</code>.{{NoteTag

|While the latter modification is not mentioned by {{harvtxt|Bentley|1989}} does not mention this difference, itusing achieves<code>x</code> maintaininginstead of <code>0</code> in the modified[[#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.

}}

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

current_sum = max(x0, current_sum + x)

</syntaxhighlight>

In that case, if the input contains no positive element, the returned value is that of the largest element (i.e., the value closest to 0), or negative infinity if the input was empty. For correctness, an exception should be raised when the input array is empty, since an empty array has no maximum nonempty subarray. If the array is non-empty, its first element can be used in place of negative infinity, if needed to avoid mixing numeric and non-numeric values.

As a [[loop invariant]], in the <math>j</math>th step, the old value of <code>current_sum</code> holds the maximum over all <math>i \in \{ 1,\ldots, j \}</math> of the sum <math>A[i]+\cdots+A[j-1]</math>.{{NoteTag

|This sum is <math>0</math> when <math>i=j</math>, corresponding to the empty subarray <math>A[j\ldots j-1]</math>.

}}

Therefore, <code>current_sum</code><math>+A[j]</math>

is the maximum over all <math>i \in \{ 1,\ldots, j \}</math> of the sum <math>A[i]+\cdots+A[j]</math>. To extend the latter maximum to cover also the case <math>i=j+1</math>, it is sufficient to consider also the empty subarray <math>A[j+1 \; \ldots \; j]</math>. This is done in line 6 by assigning <math>\max(0,</math><code>current_sum</code><math>+A[j])</math> as the new value of <code>current_sum</code>, which after that holds the maximum over all <math>i \in \{ 1, \ldots, j+1 \}</math> of the sum <math>A[i]+\cdots+A[j]</math>. Machine-verified [[C (programming language)|C]] / [[Frama-C]] code of both variants can be found [[:commons:File:Kadane run −2,1,−3,4,−1,2,1,−5,4.gif#Source code|here]].

===Computing the best subarray's position===