Problem. Finding the contiguous run of numbers with the largest sum, when the array can mix positive and negative values, so you cannot just take everything or nothing.
Baseline complexity. Checking every possible start and end pair costs O(n^2) time, because there are on the order of n^2/2 subarrays to sum.
Solution. Kadane’s algorithm carries a single running sum forward, discarding it and starting fresh the moment it turns negative, cutting the work to one O(n) pass with O(1) extra memory.
Measured result. On a Raspberry Pi running CPython 3.13.5, the O(n) version was already about 79 times faster than the O(n^2) brute force at 200 elements and around 1,672 times faster at 3,200 elements, matching the widening gap the complexity difference predicts.[1]
Reproduce the result
Complete code
"""Benchmark: brute-force maximum subarray sum vs Kadane's algorithm.Correctness is checked against a third, independent O(n^2) prefix-sumreference before any timing is reported. Only after all three implementationsagree on every trial does the script move on to measuring wall-clock timewith timeit, using the documented Timer.repeat() pattern and reporting theminimum of the samples, as the Python documentation recommends."""from __future__ import annotationsimport jsonimport platformimport randomimport sysimport timeitdef brute_force(a: list[int]) -> int: """O(n^2): check every contiguous subarray sum directly.""" n = len(a) best = a[0] for i in range(n): total = 0 for j in range(i, n): total += a[j] if total > best: best = total return bestdef prefix_sum_reference(a: list[int]) -> int: """O(n^2) but built from prefix sums, used only as an independent check.""" n = len(a) prefix = [0] * (n + 1) for i, v in enumerate(a): prefix[i + 1] = prefix[i] + v best = a[0] for i in range(n): for j in range(i + 1, n + 1): total = prefix[j] - prefix[i] if total > best: best = total return bestdef kadane(a: list[int]) -> int: """O(n) time, O(1) extra space: Kadane's algorithm.""" best = current = a[0] for x in a[1:]: current = x if current < 0 else current + x if current > best: best = current return bestdef run_correctness_checks(seed: int, trials: int = 200, max_len: int = 60) -> dict: rng = random.Random(seed) mismatches = [] for t in range(trials): n = rng.randint(1, max_len) arr = [rng.randint(-50, 50) for _ in range(n)] r_brute = brute_force(arr) r_ref = prefix_sum_reference(arr) r_kadane = kadane(arr) if not (r_brute == r_ref == r_kadane): mismatches.append({"trial": t, "array": arr, "brute": r_brute, "ref": r_ref, "kadane": r_kadane}) return {"trials": trials, "max_len": max_len, "seed": seed, "mismatches": mismatches, "all_agree": len(mismatches) == 0}def build_array(n: int, seed: int) -> list[int]: rng = random.Random(seed) return [rng.randint(-1000, 1000) for _ in range(n)]def main() -> None: seed = 20260923 correctness = run_correctness_checks(seed=seed) if not correctness["all_agree"]: print(json.dumps({"error": "correctness_check_failed", "detail": correctness}, indent=2)) sys.exit(1) sizes = [200, 400, 800, 1600, 3200] repeat = 5 number = 3 results = [] for n in sizes: arr = build_array(n, seed=seed + n) # Sanity: brute force and Kadane must still agree at this size before timing it. assert brute_force(arr) == kadane(arr) brute_times = timeit.repeat(lambda: brute_force(arr), repeat=repeat, number=number) kadane_times = timeit.repeat(lambda: kadane(arr), repeat=repeat, number=number) brute_best = min(brute_times) / number kadane_best = min(kadane_times) / number results.append({ "n": n, "brute_force_seconds_per_call": brute_best, "kadane_seconds_per_call": kadane_best, "speedup": brute_best / kadane_best if kadane_best > 0 else None, "brute_force_all_samples": brute_times, "kadane_all_samples": kadane_times, }) output = { "correctness": { "trials": correctness["trials"], "max_len": correctness["max_len"], "seed": correctness["seed"], "all_agree": correctness["all_agree"], }, "timing_methodology": { "repeat": repeat, "number": number, "reported_value": "min(timeit.repeat(...)) / number, per Python timeit documentation", "note": "GC left at default (enabled off during timing, per timeit's own default); array constructed once per size and reused across repeats.", }, "python_version": sys.version, "platform": platform.platform(), "processor": platform.processor() or platform.machine(), "results": results, } print(json.dumps(output, indent=2))if __name__ == "__main__": main()
Output
{ "correctness": { "trials": 200, "max_len": 60, "seed": 20260923, "all_agree": true }, "timing_methodology": { "repeat": 5, "number": 3, "reported_value": "min(timeit.repeat(...)) / number, per Python timeit documentation", "note": "GC left at default (enabled off during timing, per timeit's own default); array constructed once per size and reused across repeats." }, "python_version": "3.13.5 (main, Jul 15 2026, 20:25:40) [GCC 14.2.0]", "platform": "Linux-6.12.47+rpt-rpi-v8-aarch64-with-glibc2.41", "processor": "aarch64", "results": [ { "n": 200, "brute_force_seconds_per_call": 0.0025513010720411935, "kadane_seconds_per_call": 3.243812049428622e-05, "speedup": 78.6513223690192, "brute_force_all_samples": [ 0.007724847178906202, 0.007689495105296373, 0.007653903216123581, 0.007713607046753168, 0.0076588839292526245 ], "kadane_all_samples": [ 0.00011157384142279625, 0.00011899881064891815, 9.835092350840569e-05, 9.731436148285866e-05, 9.74796712398529e-05 ] }, { "n": 400, "brute_force_seconds_per_call": 0.01196296171595653, "kadane_seconds_per_call": 6.259201715389888e-05, "speedup": 191.1259975300437, "brute_force_all_samples": [ 0.03640429023653269, 0.036867452785372734, 0.03595986682921648, 0.03624325431883335, 0.03588888514786959 ], "kadane_all_samples": [ 0.00020805373787879944, 0.00021466519683599472, 0.00018955394625663757, 0.00018777605146169662, 0.00018810993060469627 ] }, { "n": 800, "brute_force_seconds_per_call": 0.05206704931333661, "kadane_seconds_per_call": 0.00012762239202857018, "speedup": 407.97738144322375, "brute_force_all_samples": [ 0.15735167590901256, 0.1646814150735736, 0.16041333740577102, 0.15620114794000983, 0.15637546125799417 ], "kadane_all_samples": [ 0.00040868204087018967, 0.00038458965718746185, 0.0003828671760857105, 0.0004166262224316597, 0.0003843107260763645 ] }, { "n": 1600, "brute_force_seconds_per_call": 0.21228370893125734, "kadane_seconds_per_call": 0.00025259066993991536, "speedup": 840.4257725819961, "brute_force_all_samples": [ 0.6376976198516786, 0.6474578026682138, 0.6390671660192311, 0.636851126793772, 0.6395865129306912 ], "kadane_all_samples": [ 0.0007808273658156395, 0.000757772009819746, 0.0008172709494829178, 0.0008728820830583572, 0.0007604020647704601 ] }, { "n": 3200, "brute_force_seconds_per_call": 0.8486826132672528, "kadane_seconds_per_call": 0.0005074526804188887, "speedup": 1672.4369503116782, "brute_force_all_samples": [ 2.554313530214131, 2.5909042079001665, 2.5522152348421514, 2.5460478398017585, 2.597498401068151 ], "kadane_all_samples": [ 0.0015610437840223312, 0.0015223580412566662, 0.0015614130534231663, 0.0015524872578680515, 0.0015705428086221218 ] } ]}
Environment
CPython 3.13.5 on Linux 6.12.47+rpt-rpi-v8 (aarch64), a Raspberry Pi. No third-party packages: the benchmark uses only the standard library timeit module.[2]
Methodology
Arrays of five sizes (200, 400, 800, 1,600 and 3,200 elements) were built once per size with random.Random(seed) using integers between -1,000 and 1,000, then reused for every timing sample at that size so the comparison is not exposed to different inputs. Before any timing ran, both implementations were checked for agreement against a third, independently coded O(n^2) reference built from prefix sums, across 200 randomly generated arrays of up to 60 elements. Timing used timeit.repeat() with repeat=5 and number=3, and each reported figure is min(samples) / number, which is the value the Python documentation recommends over a mean, since the minimum reflects the fastest the machine could run the code with the least noise from other processes.[2]
The problem
An array such as [-2, 1, -3, 4, -1, 2, 1, -5, 4] does not let you just sum everything, because two of the entries are negative enough to drag the total down. The best contiguous run here is [4, -1, 2, 1], with a sum of 6. If the whole array were non-negative the answer would trivially be the whole array, and if it were all non-positive the best you could do is pick the single largest (least negative) value. The interesting case sits in between, when the array mixes signs and the boundaries of the best run are not obvious without checking.
The maximum subarray problem was proposed by Ulf Grenander in 1977 as a simplified one-dimensional stand-in for a two-dimensional pattern-detection problem in digitised images. Grenander’s own one-dimensional solution ran in O(n^2) using prefix sums. Michael Shamos then produced an O(n log n) divide-and-conquer version overnight, and when he described the problem at a Carnegie Mellon seminar, Jay Kadane designed the O(n) single-pass algorithm within a minute, which is the fastest asymptotic complexity possible for a problem that has to look at every element at least once.[1]
Baseline complexity
The brute-force approach in the benchmark tries every start index i and, for each one, extends the end index j one step at a time, keeping a running total:
for i in range(n):
total = 0
for j in range(i, n):
total += a[j]
best = max(best, total)The outer loop runs n times and the inner loop runs, on average, about n/2 times, so the total work is proportional to n^2/2, which is O(n^2). This is already an improvement over summing each subarray from scratch (which would be O(n^3)), because the running total avoids re-adding the same elements. But it still repeats work across different values of i: every element gets re-examined for every starting point to its left.
The solution
Kadane’s algorithm keeps exactly one number in flight: the best sum of a subarray ending at the current position. Moving to the next element, there are only two sensible choices: either extend the previous best-ending-here subarray by adding the new element, or start a brand new subarray at the new element alone. Whichever gives the larger value becomes the new “best ending here”:
current = a[0]
for x in a[1:]:
current = x if current < 0 else current + x
best = max(best, current)The current < 0 check is the key move: if the running sum has gone negative, it can only drag down anything added after it, so restarting from the new element is always at least as good as keeping the negative prefix. Because this decision touches each element exactly once and needs no extra storage beyond two running variables, the algorithm is O(n) time and O(1) space, which is the same complexity class as simply reading the array once.
What the measurement shows
Correctness came first: 200 randomly generated arrays, up to 60 elements each, were checked with three independent implementations (the O(n^2) brute force, an O(n^2) prefix-sum reference, and Kadane’s O(n) version), and all three agreed on every trial before any timing began. That rules out a fast-but-wrong result skewing the comparison.
The timed results follow the shape the complexity analysis predicts. At n=200 the brute force averaged roughly 2.55 ms per call against about 0.032 ms for Kadane’s algorithm, a ratio near 79x. By n=3,200 the brute force cost had grown to roughly 849 ms per call while Kadane’s algorithm stayed under 0.51 ms, a ratio near 1,672x. Because the brute force is quadratic and Kadane’s algorithm is linear, doubling n roughly quadruples the brute-force cost while only doubling Kadane’s, which is exactly the widening gap the five data points show.
Where it stops helping
Kadane’s algorithm answers one specific question: the maximum sum of any contiguous subarray, given that at least one element must be included (an empty array is undefined here, and the implementation above will raise on an empty list because a[0] fails). It does not track a required minimum or maximum subarray length, and if a version that reports the actual start and end indices is needed, that requires holding two extra index variables and updating them alongside current and best, which is a small addition but not included in the benchmark above.
The O(1) space claim describes the algorithm itself, not necessarily every Python implementation of it. The code shown allocates no additional lists or arrays proportional to n, and the timings reflect that: memory use does not grow with input size the way the brute force’s total-recomputation pattern might suggest, though this benchmark measured wall-clock time only, not memory. For arrays that are entirely non-negative, both approaches degrade to summing the whole array, and the practical speed gap will be smaller because the brute force’s inner loop then spends less time being cut short by nothing (there is nothing to cut short); the comparison here specifically used arrays with a full spread of positive and negative values, which is the case where a poor baseline does the most unnecessary work.
