Efficient bucketing of numbers
Polynomial time is not too difficult. 

A "cluster" contains a sequence of 1 or more consecutive numbers from your list. The "badness" of a cluster is defined as the sum of absolute differences between the numbers, and the average of the numbers in the cluster. A sequence of clusters is a list of clusters, containing consecutive numbers from the list starting with the first one. And the "badness" of a sequence of clusters is the sum of badnesses of the individual clusters. 

First get a reasonable upper bound for the best clustering to avoid unnecessary work: Just cluster the n numbers into m buckets of equal or almost equal size, then calculate the badness of this sequence of clusters. Call the result B. You might also calculate the badness of a sequence of clusters created by splitting where the largest gaps between consecutive numbers are. 

Now for 1 ≤ m' ≤ m, and for 1 ≤ n' ≤ n - (m - m'), calculate the best sequence of m' clusters covering exactly the first n' numbers, and its badness. For m' = 1 that's trivial, because the cluster consists of the numbers 1 to n'. For m' > 1 it is more difficult: The best clustering using m' clusters to cover 1 to n' consists of the best clustering using m'-1 clusters covering 1 to n'' for some n'' &lt; n', plus the cluster n''+1 .. n'. You calculate the badness of this for n'' = n'-1 down to m'-1. All these badnesses can be calculated in O (n), so the best badness for m' and n' can be found in O (n). 

In total, you find the optimal badness for m clusters covering 1 to n in $O (n^3)$. If you take advantage of the upper bound B found earlier, and consider that any result that leads to a badness > B can be ignored, you can probably save significant amount of time. 

PS. How to find the badness for different clusters each in constant time: Let's say you want to find the badness of a cluster covering the numbers from l to r, for l = r, r-1, r-2, ..., 1. Start with l = r. The sum of items in the cluster is $C = a_l$. The badness is 0. Let s = l. Then the sum of items at indices &lt; s is $S = 0$. 

Now replace l with l-1. Increase C and S by $a_l$. The average A of items in the cluster is C / (r - l + 1). As long as $a_{s-1} ≥ A$ replace s with s-1, and subtract $a_s$ from S. The badness in the cluster is C - 2S + ((2s - l - n - 1)A (unless I made some mistake).