Maximum subarray problem: Difference between revisions

Revision as of 20:40, 31 March 2023

Revision as of 03:52, 1 April 2023

Line 58:

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 \}</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 611 by assigning <math>\max(0best_sum,</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}}{{sfn|Gries|1982|p=211}} expressed here in [[Python (programming language)|Python]]:

Line 65:

def max_subarray(numbers):

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

best_sumif =not 0numbers:

"""Return nothing when an empty array is passed."""

current_sum = 0

return None

"""Setting initial values to max negative in Python (-2 ** 31)"""

best_sum = (-2 ** 31)

current_sum = 0(-2 ** 31)

for x in numbers:

current_sum = max(0x, current_sum + x)

best_sum = max(best_sum, current_sum)

return best_sum

</syntaxhighlight>

The code implementation assumes a max integer value (positive and negative) of 2,147,483,648.

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

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.

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 empty subarrays admitted===

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}} and also in the for loop <code>current_sum</code> should be updated as <code>max(x, current_sum + x)</code>.{{NoteTag

|While the latter modification is not mentioned by {{harvtxt|Bentley|1989}}, it achieves maintaining the modified loop invariant <code>current_sum</code><math>=\max_{i \in \{ 1, ..., j \}} A[i]+...+A[j]</math> at the beginning of the <math>j</math>th step.

}}

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.

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