Stream: Mirror: Isabelle Users Mailing List

Topic: [isabelle] New in the AFP: Maximum Segment Sum

view this post on Zulip Email Gateway (Sep 30 2022 at 20:38):

From: Tobias Nipkow <nipkow@in.tum.de>
Maximum Segment Sum
Nils Cremer

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
(O(n^2)) and Kadane's algorithm (O(n)) are given and their correctness is proved.

https://www.isa-afp.org/entries/Maximum_Segment_Sum.html

Enjoy!
smime.p7s

Last updated: Apr 24 2024 at 01:07 UTC