k-subset with maximal variance I have two versions of the same question:


*

*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"?

*Given a set of numbers, how do I select from that set a list of k numbers that maximize the variance?

 A: When the numbers are sorted there's a simple $O(k)$ algorithm, because when $k\gt1,$ some variance-maximizing subset will consist of the $k_0\ge 1$ smallest and $k−k_0$ largest elements, whence a search over $k_0=1,\ldots,k−1$ does the trick.
(Even when the $n$ numbers are not sorted, finding the $k^\text{th}$ largest or smallest element takes $O(n)$ effort, so the algorithm is at worst $O(k n)$ or $O(n\log n)$, whichever is smaller.)

By understanding how changing a single value changes the variance, we can see immediately why this is.  Consider any $k$ numbers $x_1, \ldots, x_k$.  Contemplate changing $x_k$ to $x_k+\delta$ for some number $\delta$.   Because the original mean is
$$\bar x = \frac{1}{k}(x_1+\cdots+x_k),$$
adding $\delta$ changes it to
$$\bar x^\prime = \bar x + \frac{1}{k}\delta.\tag{1}$$
Because the original variance, multiplied by $k$, is
$$ks^2 = (x_1^2 + \cdots + x_k^2) - k\bar x^2,$$
we may directly compute the effect of adding $\delta$ to the sum of squares (it affects only the last square) and exploit $(1)$ to determine how the variance changes:
$$\eqalign{
ks^{\prime 2} - ks^2 &= [(x_k+\delta)^2 - x_k^2] - k[\bar x^{\prime 2} - \bar x^2]\\
&= 2\delta(x_k - \bar x) + \frac{k-1}{k}\delta^2 \ge 2\delta(x_k - \bar x).
}$$
This will be nonnegative whenever the signs of $\delta$ and $x_k-\bar x$ are the same.  In other words, 

if we can manage to move $x_k$ further from the mean, we will increase the variance.

Now suppose we have identified a variance-maximizing sequence $\mathcal A$ of $k$ values chosen from a sequence $X$ of given values.  It should be clear--and is easy to demonstrate formally--that if $\mathcal A$ does not consist of the very smallest and the very largest elements of $X$--then we can select some $x\in\mathcal A$ that comes from somewhere in the middle of $X$ and replace it by another element $y\in X\setminus \mathcal A$ that is at least as far from the mean of $\mathcal A$ as $x$ itself is.  This replacement would be tantamount to adding the value $\delta = y-x$ to $x$, and (by the foregoing calculations) would produce another variance-maximizing subsequence.
That's it: after a finite number of such moves, we would no longer be able to find such an $x$.  At this point, $\mathcal A$ would be the union of two extreme "tails" of $X$, as claimed.
Similar reasoning shows that $\mathcal A$ will not consist of just one tail of $X$ (unless $\mathcal A$ were all of $X$ itself or the elements of $X$ were all equal), for by replacing the most "inner" element of $\mathcal A$ by the extreme element in the same direction, we would not decrease the variance. 
