|
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 modifiedadapted to the case which disallows empty subarrays or to keep track of the starting and ending indices of the maximum subarray . as well: ▼===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}} 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.
}}
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 subarray:
<syntaxhighlight lang="python" line="1">
def max_subarray(numbers):
"""Find the largest sum of any contiguous subarray."""
if numbers == []:
raise ValueError('Empty array has no nonempty subarrays')
best_sum = float('-inf')
current_sum = 0
for x in numbers:
current_sum = max(x, current_sum + x)
best_sum = max(best_sum, current_sum)
return best_sum
</syntaxhighlight>
===Conditionally admitting empty subarrays===
The only case when it matters if empty subarrays are admitted, is if all numbers in the input array are negative. In this case, the maximum subarray will either be empty (when empty subarrays are allowed), or contain the largest number in the input array (when empty subarrays are not allowed).
An alternative algorithm that admits empty subarrays is easily developed from the algorithm given above which does not admit empty subarrays: The only change that is needed is to return <code>max(best_sum, 0)</code> instead of <code>best_sum</code>. It can be seen that this version is correct:
* For an empty input array the previous algorithm will return minus infinity, so this algorithm will return zero, which corresponds to the sum of elements of an empty subarray.
* For an input array with only negative numbers, the previous algorithm will return the largest of the integers, which is negative. So this algorithm will return zero, which corresponds to the sum of elements of an empty subarray.
* For all other cases, there is at least one nonnegative integer in the output, so there is a nonempty subarray for which the sum of the elements is at least 0. Since the sum of the elements is always zero for empty subarrays, it doesn't matter if empty subarrays are admitted or not, so this algorithm correctly returns the same answer as the previous algorithm gives.
This algorithm can also be converted to a version that conditionally admits empty subarrays, based on a parameter: If empty subarrays are admitted, return <code>max(0, best_sum)</code>, otherwise, return <code>best_sum</code>. An exception should be raised the input array is empty but empty subarrays are not admitted:
<syntaxhighlight lang="python" line="1">
def max_subarray(numbers, admit_empty_subarrays=True):
"""Find the largest sum of any contiguous subarray."""
if not(admit_empty_subarrays) and numbers == []:
raise ValueError('Empty array has no nonempty subarrays')
best_sum = float('-inf')
current_sum = 0
for x in numbers:
current_sum = max(x, current_sum + x)
best_sum = max(best_sum, current_sum)
if admit_empty_subarrays:
best_sum = max(0, best_sum)
return best_sum
</syntaxhighlight>
===Computing the best subarray's position===
▲The algorithm can be modified to keep track of the starting and ending indices of the maximum subarray as well:
<syntaxhighlight lang="python" line="1">
def max_subarray(numbers):
"""Find a contiguous subarray with the largest sum."""
best_sum = 0 # or: float('-inf')
best_start = best_end = 0 # or: None
current_sum = 0
for current_end, x in enumerate(numbers):
if current_sum <= 0:
# Start a new sequence at the current element
current_start = current_end
current_sum = x
else:
# Extend the existing sequence with the current element
current_sum += x
if current_sum > best_sum:
best_sum = current_sum
best_start = current_start
best_end = current_end + 1 # the +1 is to make 'best_end' match Python's slice convention (endpoint excluded)
return best_sum, best_start, best_end
</syntaxhighlight>
In Python, arrays are indexed starting from 0, and slices exclude the endpoint, so that the subarray [22, 33] in the array a=[-11, 22, 33, -44] would be expressed as a[1:3].
Because of the way this algorithm uses optimal substructures (the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem: the maximum subarray ending at the previous position) this algorithm can be viewed as a simple/trivial example of [[dynamic programming]].
===Complexity===
The runtime complexity of Kadane's algorithm is <math>O(n)</math>.{{sfn|Bentley|1989|p=74}}{{sfn|Gries|1982|p=211}}
| 