Kadane's algorithm in Python
Linear-time dynamic program that scans once, tracking the best sum of a subarray ending at each position.
- File
kadane_algorithm.py, 45 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/kadane-algorithm/. The authors are listed in prov/W9Q826.jsonl.
from typing import Union
Number = Union[int, float]
def kadane(a: list[Number]) -> tuple[Number, int, int]:
"""Return (best, i, j) with sum(a[i:j + 1]) == best, the largest sum of a non-empty subarray.
Indices are 0-based and inclusive. Among the best subarrays, the one with the
earliest end is returned, and for that end the earliest start.
Precondition: a is not empty (raises ValueError otherwise).
Cost: O(n) time, O(1) extra space.
"""
if not a:
raise ValueError("the array must not be empty")
cur = a[0] # @line L1
c = 0
best = a[0]
bi, bj = 0, 0
for j in range(1, len(a)): # @line L2
if cur < 0: # @line L3
cur = a[j]
c = j
else: # @line L4
cur = cur + a[j]
if cur > best: # @line L5
best = cur
bi, bj = c, j
return best, bi, bj # @line L6
def kadane_allow_empty(a: list[Number]) -> Number:
"""Return the largest subarray sum when the empty subarray (sum 0) is allowed.
Cost: O(n) time, O(1) extra space. Returns 0 for an empty array.
"""
cur: Number = 0
best: Number = 0
for x in a:
cur = max(cur, 0) + x
best = max(best, cur)
return best
test_kadane_algorithm.py 45 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/kadane-algorithm/. The authors are listed in prov/W9Q826.jsonl.
import random
import pytest
from kadane_algorithm import kadane, kadane_allow_empty
def brute(a: list[int]) -> int:
return max(sum(a[i : j + 1]) for i in range(len(a)) for j in range(i, len(a)))
def test_example() -> None:
assert kadane([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == (6, 3, 6)
assert kadane([31, -41, 59, 26, -53, 58, 97, -93, -23, 84]) == (187, 2, 6)
clrs = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
assert kadane(clrs) == (43, 7, 10)
def test_edges() -> None:
assert kadane([5]) == (5, 0, 0)
assert kadane([-5]) == (-5, 0, 0)
assert kadane([-3, -1, -2]) == (-1, 1, 1)
assert kadane_allow_empty([-3, -1, -2]) == 0
assert kadane_allow_empty([]) == 0
assert kadane([0, 0, 0]) == (0, 0, 0)
assert kadane([1, 2, 3]) == (6, 0, 2)
assert kadane([2, -2, 2]) == (2, 0, 0)
assert kadane([1.5, -0.5, 2.0]) == (3.0, 0, 2)
with pytest.raises(ValueError):
kadane([])
def test_against_brute_force() -> None:
rng = random.Random(20261105)
for _ in range(3000):
n = rng.randrange(1, 25)
a = [rng.randrange(-10, 11) for _ in range(n)]
best, i, j = kadane(a)
assert best == brute(a)
assert 0 <= i <= j < n
assert sum(a[i : j + 1]) == best
assert kadane_allow_empty(a) == max(best, 0)
What the next level needs
- the tests did not run in this build