Maximum subarray problem: Difference between revisions

Revision as of 16:12, 30 June 2023

Revision as of 19:51, 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 below 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>