Maximum subarray problem: Difference between revisions

Revision as of 07:53, 26 February 2025

Latest revision as of 15:17, 26 February 2025

Line 79:

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

In such variant, the answer is 0 when the input contains no positive elements (including when the input is empty).

The solutionvariant is obtained with 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;