Maximally Dense Segments

Speaker: Shin-Cheng Mu (Academia Sinica, Taiwan)

Abstract: Given a list of numbers, the task is to find a consecutive segment whose average (sum divided by length) is maximum. This "maximally dense segment" appears to be an easy generalisation of the well-known maximum segment sum problem, but its solution turns out to be much harder than it looks. We extend and illuminate some recent work on this problem with a formal development of a linear-time online algorithm. In this talk, I will mainly be giving an intuition of the problem and its algorithm using diagrams, and explain why this problem is hard.