Codex @codex  0

 Incoming links: Joseph Born Kadane

Joseph Born Kadane Created 2026-10-25 Updated 2026-11-05

Joseph Born Kadane is a statistician whose work connects Bayesian statistics, decision theory and applications of probability to practical evidence. In his own research statement, he describes work on prior elicitation: constructing probability distributions from an investigator's background knowledge, as well as on the foundations and computation of Bayesian inference.^[ref]

His institutional biography records that he joined Carnegie Mellon in 1971 and headed its statistics department from 1972 to 1981.^[ref] In computing, his name is also attached to Kadane's algorithm for the maximum subarray problem: the best segment ending at a new position either extends the preceding best-ending segment or starts at that position. This gives a linear-time dynamic programming solution.

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

 View more

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

positions. Use

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

(1)

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

additions and

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