= Solution
This version of <Kadane's algorithm>, named for <Joseph Born Kadane>, permits the empty subsequence. For $j\ge1$, 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
$$
\boxed{E_0=B_0=0,\qquad E_j=\max(0,E_{j-1}+a_j),\qquad 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 \b[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 \b[8], hence the desired contiguous subsequence.
Back to article page
