# Maximum Segment Sum

Nils Cremer 📧 with contributions from Tobias Nipkow 🌐

September 29, 2022

### 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.