Maximum subarray problem: Difference between revisions

Revision as of 16:32, 4 April 2023

Revision as of 16:59, 4 April 2023

Line 63:

<syntaxhighlight lang="python" line>

def max_subarray1max_subarray(numbers):

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

ifbest_sum not= numbers:0

current_sum = (-2 ** 31)0

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

return None

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

best_sum = (-2 ** 31)

current_sum = (-2 ** 31)

for x in numbers:

current_sum = max(x0, current_sum + x)

best_sum = max(best_sum, current_sum)

return best_sum

</syntaxhighlight>

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

The code implementation assumes a max integer value (positive and negative) of 2,147,483,648 as programmatic placeholders for (positive and negative) infinity. This can be modified in Python as numbers are dynamic in size.

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}}

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

best_sum = (-2 ** 31)infinity;

</syntaxhighlight>

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.

}}

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

current_sum = max(x, 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.

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