Calculating a linear-time solution to the densest-segment problem. (14th December 2015) - CURTIS, SHARON; MU, SHIN-CHENG
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.