# Maximizing sum and product of an array

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$$

• 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? Commented Nov 4, 2023 at 16:56
• @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.
– vhd
Commented Nov 4, 2023 at 17:24
• 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. Commented Nov 4, 2023 at 17:47
• 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
– vhd
Commented Nov 4, 2023 at 18:04
• 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. Commented Nov 4, 2023 at 20:08

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.