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

This version of Kadane's algorithm, named for Joseph Born Kadane, permits the empty subsequence. For $j\ge 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. UseA 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: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.