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.