Maximum subarray problem: Difference between revisions

Revision as of 04:15, 1 April 2023

Revision as of 07:25, 2 April 2023

Line 79:

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