# k-subset with maximal variance

I have two versions of the same question:

1. Given a list of numbers (with possible duplicates), how to find a k-subset (with possible duplicates) that maximize the variance? is there a more efficient way than the obvious "check-all-k-subsets"?
2. Given a set of numbers, how do I select from that set a list of k numbers that maximize the variance?
-
I believe there's a simple $O(k)$ algorithm, because when $k \gt 1$, a variance-maximizing subset must consist of the $k_0$ smallest and $k-k_1$ largest elements, whence a search over $k_0=1,2,\ldots,k-1$ does the trick. –  whuber Mar 16 '12 at 19:37
Don't forget about computing the $k$ smallest and largest elements of the input, this requires $O(n \log k)$. –  krlmlr Mar 19 '12 at 3:05
Good point, @user. Regardless, these execution times ($O(k)$ for a pre-sorted list and $O(n\log(k))$ otherwise) are very small compared to the number of $k$-subsets of $n$ whenever $k\gt 1$. –  whuber Mar 19 '12 at 17:29