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

### License

BSD License

### Topics

- Computer science/Algorithms

### Session Maximum_Segment_Sum

- Maximum_Segment_Sum

## Cite

×

Maximum_Segment_Sum-AFP

    @article{Maximum_Segment_Sum-AFP,
      author  = {Nils Cremer},
      title   = {Maximum Segment Sum},
      journal = {Archive of Formal Proofs},
      month   = {September},
      year    = {2022},
      note    = {\url{https://isa-afp.org/entries/Maximum_Segment_Sum.html},
                 Formal proof development},
      ISSN    = {2150-914x},
    }

Download

## Download

× Download latest

Older releases:

- Sep 13, 2023 : Isabelle2023
- Oct 27, 2022 : Isabelle2022
- Sep 30, 2022 : Isabelle2021-1