Maximizing sum and product of an array

Question

Given an array of positive numbers with allowed replication, what is the algorithm to find the max amount possible only with summing or multiplying elements? All numbers must be involved in some operation.

I don't know how to look at this problem with greedy approach.

For example, given the array $[1, 1, 1, 1, 2, 2, 2, 3]$. The maximum amount is possible using the following set of operations: $(2+1) \cdot (2+1) \cdot (2+1) \cdot (3+1) = 108$

• Steven: Are the numbers real, integers, positive? Do all numbers need to be involved in some operations, or only a subset of choice? Do the operations need to use the numbers in the same order of the array? Finally, what did you try to solve the problem?
• vhd: @Steven Positive integers. All numbers should ne added or multiplied by some other number from array and put result in array instead of elements used. I don't know how to look at this problem greedy.
• Jörg W Mittag: This sounds like a pretty boring problem. Except for 1, multiplying will always give you a bigger increase than adding, so the algorithm is simply: add all the 1s, multiply everything else.
• vhd: Wrong. You have 1 1 1 1 2 2 2 3. Based on what you said it's 96. But it can go upto 108
• Jörg W Mittag: According to the problem specification, that is not allowed: the problem specification says "only with summing or multiplying elements", but you are not multiplying elements, you are multiplying sums of elements. So, the solution you present is invalid according to the problem specification.

Answer 1

Let the array contains $n$ elements. We use the following four lemmas/observations to design an $O(n^3)$ time algorithm.

Lemma 1: In any optimal solution $O$, if there is any addition operation $a + b$, then either $a = 1$ or $b = 1$. The vice-versa statement is true as well. That is, if the array contains 1ドル$, then in any optimal solution $O$, 1ドル$ must be part of an addition operation.

Proof: ($\to$) For the sake of contradiction assume that $a > 1$ and $b > 1$. Then, replacing $a+b$ with $a \cdot b$ gives a solution with the higher value. Thus, contradicting that $O$ is an optimal solution.

($\gets$) For the sake of contradiction assume that the array contains 1ドル$ and the optimal solution has a multiplication operation $a \cdot 1$ for some element $a$. Then, replacing $a \cdot 1$ with $a + 1$ gives a solution with the higher value. Thus, contradicting that $O$ is an optimal solution.

Lemma 2: There exists an optimal solution where all the addition operations happen before the multiplication operations.

Proof: For the sake of contradiction, assume that in some optimal solution $O$ there is a multiplication operation followed by an addition operation. Let $a$ and $b$ be the elements involved in multiplication operation. Then, there are two possibilities:

1. Addition operation is done on the output of $a \cdot b$ with some element $c$. That is, $a \cdot b + c$. In this case, $(a+c) \cdot b \geq a \cdot b + c$ since $b$ is a positive integer. There are further two possibilities. The first is that if $(a+c) \cdot b > a \cdot b + c$, then replacing $a \cdot b + c$ with $(a+c) \cdot b$ gives a solution with the higher value. Thus, $O$ is not optimal, which is a contradiction. The second possibility is that $(a+c) \cdot b = a \cdot b + c$. In this case, the order of the operations can be swapped and the value of the solution does not change.
2. Addition operation is not done on the output of $a \cdot b$; it is done between some elements $c$ and $d$, i.e., $c + d$. In this case the order of the multiplication and addition operations can be swapped and the value of the solution does not change.

Lemma 3: In any solution, if there are two addition operations on any variable $a > 1$, then $(a + 1 + 1)$ can be replaced with $a\cdot(1+1)$. It will only increase the value of the solution or keeps it the same. Thus, we can assume that in an optimal solution there cannot be two or more addition operations on any variable $a > 1$. In a similar manner, we can show that there cannot be three addition operations on any variable $a = 1$.

Lemma 4: Let $a$ and $b$ be the elements such that $b \geq a > 1$. Then, $(a+1) \cdot b \geq a \cdot (b+1)$. (the proof is trivial)

Based on the above lemmas, the following is a simple greedy algorithm for the problem:

1. If all elements in the array are strictly greater than 1ドル$, then the optimal solution does not contain any addition operation (using Lemma 1ドル$). Thus, the algorithm simply multiplies the elements of the array to get the optimal solution.
2. If the array contains $p > 0$ elements of the value 1ドル$. Let the set of remaining elements be denoted by $S$. By Lemma 1ドル$ and Lemma 2ドル$, there exists an optimal solution where all the initial operations are addition operations and all the 1ドル$s are one of the operands of these addition operations. By Lemma 3ドル$, there cannot be three addition operations on any 1ドル$. Therefore, all the 1ドル$s can only form the elements of value 3ドル$ or 2ドル$ using the addition operations among themselves. Let $k$ and $\ell$ be the number of 2ドル$s and 3ドル$s obtained using addition operations on 1ドル$s. The algorithm guesses the value of $k$ and $\ell$. The remaining $p' := p - 2k -3 \ell$ elements of value 1ドル$s are directly added with the elements in set $S$. Note that using Lemma 3ドル$, we have that no element in set $S$ can have two or more addition operations. Therefore, by Lemma 4ドル$, the algorithm adds 1ドル$ to each of the top $p'$ smallest elements in $S$. The algorithm does this for each value of $k$ and $\ell$; and then choose the solution with the highest value

---

Overall Running Time: $O(n^3)$.

Sorting the elements in $S$ takes $O(n \log n)$ time. Furthermore, there are $n$ possibilities for $k$ and $\ell$ each. For each possibility, finding the value of the solution takes $O(n)$ time. Thus, we get $O(n^3)$ running time.