Calculating a linear-time solution to the densest-segment problem
Sharon A. Curtis, Shin-Cheng Mu · Journal of Functional Programming · 2015
Abstract The problem of finding a densest segment of a list is similar to the well-known maximum segment sum problem, but its solution is surprisingly challenging. We give a general specification of such problems, and formally develop a linear-time online solution, using a sliding-window style algorithm. The development highlights some elegant properties of densities, involving partitions that are decreasing and all right-skew.