Minimize and maximize the product of the sum of an nCk combination of an array, with the sum of the remaining items

Question

Say you are given an array of signed integers called NUMBERS of length l. Say NUMBERS is equal to

1, 2, 3, 4, 5

where l = 5.

You want to form a sum X of any m elements of the set NUMBERS and multiply this by the sum Y of the remaining n elements for any given m, to get a result X * Y

This result is thus of the form:

(x1 + x2 + x3 +...+ xm) * (y1 + y2 +...+ yn)

where the xis are the elements of the NUMBERS array in the X sum, and the yis are the elements of the NUMBERS array in the Y sum.

To be clear:

• l = m + n
• sum(NUMBERS) = sum(X) + sum(Y)

For example, with n = 2, one way to build a result would have X be the sum of the elements 1 and 4, and thus the sum Y of the remaining m = 3 elements be 2 + 3 + 5. So we would have X = 5 and Y = 10 The result would then be the product X * Y = 5 * 10 = 50.

We want to find the most efficient way to maximize and minimize this result for a given m.

The naive approach would be to try all possible combinations for X, and return the result where (sum(NUMBERS) - sum(X)) * sum(X) is minimized and maximized. This is of complexity O(lCn).

---

Formally:

Given (n + m) signed integers, we want to minimize and maximize the result of the algebraic expression of the form:

(x1 + x2 + x3 +...+ xn) * (y1 + y2 +...+ ym)

for a fixed given n.

---

I have noticed a pattern where the minimum can usually be obtained by segregating the m smallest elements into X and the remaining larger elements into Y, and the maximum can usually be obtained by evenly distributing the smallest and largest elements in X and Y. Is there any rationale behind this, or any way to prove this?

Answer 1

This appears to be a special case of the AM GM Inequality. Simply put, it will always be the case that $\frac{X+Y}{2} \geq \sqrt{X \cdot Y}$. For your application, You already know that $\frac{X+Y}{2} = \frac{n(n+1)}{4}$ since this is the closed form of $\sum_{i=1}^{n}i$. So, any partition that sets the sum of the numbers in $X$ equal to the sum of the numbers in $Y$ will work (e.g. place every other element in $X$).

Answer 2

Consider a continuous version of the problem where you have a given length $L$ to split into two parts, and you want to maximize their product. In other words, the problem is to find the maximum of $x(L-x)$; the solution is $x=L/2$. (One way to see this is that $x(L-x)$ describes a parabola whose vertex is at $x=L/2$.)

In your case, you want to choose elements from the set that get as close as possible to this even distribution.