the article is painfully verbose, and doesn't even get into what the objective function is! (it just gives a high level description of what dynamic programming is) And the paper is worse, droning on the idea for 82 pages!! The idea is interesting, but its on the level of a programming puzzle.

The idea:

If there are k bins in a histogram. The "fitness" of a bin is

N[k] ( logN[k] − logT[k])

N[k] is the number of elements in bin k

T[k] is the width of the bin k

The fitness of a histogram is the sum of the fitnesses of all the bins. The larger the above number, the better. The optimal segmentation of the bins can be found by a simple recursion on the elements,

(Best Histogram for points 1..n) = max_j { (Best Histogram for points 1..j) + (Fitness of final bin from j...n) }

Finally, the formula has a simple interpretation. If we think of the histogram as a probability density function, we can be said to be trying to minimize the KL divergence between the histogram's distribution and the empirical distribution.