Proving NP hardness of maximum sum of means of a partition into k sets
Put each of the $k-1$ greatest numbers in their own set, and the remaining numbers all together in the $k$th set. This linear-time algorithm can be proved correct by using the following (non-strictly) improving moves to reach the specified optimal solution from any other.


Given two numbers $a&lt;b$ with $a\in S_i$ and $b\in S_j$ and $\lvert S_i\rvert\le\lvert S_j\rvert$, swap $a$ and $b$.
Given $S_i,S_j$ where $|S_i|\ne 1$ and where all of the numbers in $S_i$ are greater than or equal to all of the numbers in $S_j$, move the smallest number in $S_i$ to $S_j$. (This move does not decrease the average of $S_i$, and does not decrease the average of $S_j$.)


An alternative correctness proof uses a linear relaxation. Let the numbers be $a_1\ge\cdots\ge a_n$ and consider the following linear program.

\begin{align}
&amp;\text{maximize }\sum_{i=1}^na_ix_i\\
&amp;\text{subject to}\\
&amp;\sum_{i=1}^nx_i=k&amp;(w)\\
&amp;\forall i\in\{1,\ldots,n\},\quad-x_i\le\frac{-1}{n-(k-1)}&amp;(y_i)\\
&amp;\forall i\in\{1,\ldots,n\},\quad x_i\le1&amp;(z_i)
\end{align}

Given a partition, for all $i\in\{1,\ldots,n\}$, we can set $x_i=1/\lvert S_j\rvert$, where $a_i\in S_j$. It follows that this program is in fact a relaxation. The proposed partition sets $x_1,\ldots,x_{k-1}=1$ and $x_k,\ldots,x_n=1/(n-(k-1))$.

Here is the dual program. By weak duality, feasible solutions of this program upperbound the objective value of the primal.

\begin{align}
&amp;\text{minimize }kw+\sum_{i=1}^n\left(\frac{-y_i}{n-(k-1)}+z_i\right)\\
&amp;\text{subject to}\\
&amp;\forall i\in\{1,\ldots,n\},\quad w-y_i+z_i=a_i&amp;(x_i)\\
&amp;\forall i\in\{1,\ldots,n\},\quad y_i,z_i\ge0\\
\end{align}

Here is a feasible solution to the dual program whose objective value is equal to the previously proposed primal solution. It follows that both solutions are optimal.

\begin{align}
w&amp;=a_k\\
y_i&amp;=\begin{cases}a_k-a_i&amp;\text{if }i\in\{k,\ldots,n\}\\0&amp;\text{otherwise}\end{cases}\\
z_i&amp;=\begin{cases}a_i-a_k&amp;\text{if }i\in\{1,\:\ldots,\:k-1\}\\0&amp;\text{otherwise}\end{cases}
\end{align}