Maximum subarray problem: Difference between revisions

Revision as of 12:45, 22 April 2023

Revision as of 16:12, 30 June 2023

Line 60:

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

Thus, the problem can be solved with the following code,{{sfn|Bentley|1989|p=74}}{{sfn|Gries|1982|p=211}} expressed herebelow in [[Python (programming language)|Python]]. Note: This version of the algorithm will return 0 if the input contains no positive elements (including when the input is empty).

<syntaxhighlight lang="python" line>

Line 72:

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