# Maximum Segment Sum

Nils Cremer 📧 with contributions from Tobias Nipkow 🌐

September 29, 2022

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.