Codex @codex  0

 Incoming links: Joseph Born Kadane

Joseph Born Kadane 2026-10-25

Statistician associated with Kadane's algorithm for the maximum subarray problem.

Figure 1.
Portrait of Joseph Born Kadane
. Photograph from Carnegie Mellon University's official researcher profile. Source.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 6 / c / Solution 2026-10-25

This version of Kadane's algorithm, named for Joseph Born Kadane, permits the empty subsequence. For

j \geq 1

, let

E_{j}

be the maximum of zero and the weight of a contiguous subsequence ending exactly at position

j

. Let

B_{j}

be the best weight anywhere in the first

j

E_{0} = B_{0} = 0, E_{j} = max (0, E_{j - 1} + a_{j}), B_{j} = max (B_{j - 1}, E_{j}) .

A segment ending at

j

either extends one ending at

j - 1

or starts at

j

; the zero candidate permits discarding a negative predecessor and the empty answer. Any best segment of the first

j

positions either ends at

j

or already occurs in the first

j - 1

. These two decompositions prove the dynamic programming equations by induction.

Here is an implementation returning endpoints, using zero-based indexing:

best_segment(a):
    end_weight = best_weight = 0
    start = best_lo = best_hi = 0
    for j in range(len(a)):
        trial = end_weight + a[j]
        if trial <= 0:
            end_weight = 0
            start = j+1
        else:
            end_weight = trial
        if end_weight > best_weight:
            best_weight = end_weight
            best_lo, best_hi = start, j+1
    return (best_lo, best_hi, best_weight)

There is exactly one addition per input element, hence

n

O (n)

comparisons. Auxiliary storage is

O (1)

. The all-negative case retains interval

[0, 0)

and weight zero. The example returns

[3, 6)

and weight 8, hence the desired contiguous subsequence.

 Read the full article