**This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.**

### Abstract

In this work we consider the maximum
segment sum problem, that is to compute, given a list of
numbers, the largest of the sums of the contiguous segments of that
list. We assume that the elements of the list are not necessarily
numbers but just elements of some linearly ordered group. Both
a naive algorithm ($\mathcal{O}(n^2)$) and
Kadane's
algorithm ($\mathcal{O}(n)$) are given and their correctness
is proved.