Maximum subarray problem: Difference between revisions

Revision as of 23:20, 23 February 2025

Latest revision as of 15:17, 26 February 2025

(One intermediate revision by one other user not shown)

Line 77:

| [[File:Kadane run −2,1,−3,4,−1,2,1,−5,4.gif|thumb|500px|Execution of Kadane's algorithm on the [[#top|above]] example array. ''{{color|#0000c0|Blue}}:'' subarray with largest sum ending at ''i''; ''{{color|#00c000|green}}:'' subarray with largest sum encountered so far; a lower case letter indicates an empty array; variable ''i'' is left implicit in Python code.]]

|}

Kadane's original algorithm, solvesas originally published, is for solving the problem variant whenwhich allows empty subarrays are admitted.{{sfn|Bentley|1989|p=74}}{{sfn|Gries|1982|p=211}}

ThisIn such variant, the willanswer returnis 0 ifwhen the input contains no positive elements (including when the input is empty).

ItThe variant is obtained bywith two changes in code: in line 3, <code>best_sum</code> should be initialized to 0 to account for the empty subarray <math>A[0 \ldots -1]</math>

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

best_sum = 0;

</syntaxhighlight>

and line 6 in the for loop <code>current_sum</code> should be updated asto <code>max(0, current_sum + x)</code>.{{NoteTag

|While {{harvtxt|Bentley|1989}} does not mention this difference, using <code>x</code> instead of <code>0</code> in the [[#No empty subarrays admitted|above]] version without empty subarrays achieves maintaining its loop invariant <code>current_sum</code><math>=\max_{i \in \{ 1, ..., j-1 \}} A[i]+...+A[j-1]</math> at the beginning of the <math>j</math>th step.

}}