How fast can we optimally cluster 1-D data?
Here's what my search has come up with:

There's a straightforward dynamic programming solution of the problem in this case, which requires $\mathop{\Omega}\left( k \cdot n^3 \right)$ time; and with some thought one can avoid redundant computation of sums-of-squares by this algorithm, reducing the complexity to $\mathop{\Omega}\left( k \cdot n^2 \right)$. This is described in:


  Wang, Haizhou, and Mingzhou Song. Ckmeans. 1d. dp: optimal k-means clustering in one dimension by dynamic programming. The R journal 3, no. 2 (2011): 29.


That being said - I'm thinking perhaps this can be improved to $\mathop{o} \left( k \cdot n \log{n} \right)$ somehow, or at least $\mathop{\omega} \left( k \cdot n^2 \right)$.