Maximizing an algebraic expression using brackets

Question

It's a riddle of sorts: given a list of numbers $\alpha_1 \dots \alpha_n$ and operators $o_1 \dots o_{n-1}$ which can be only $\times\, \mbox{or}\, + $ if the above is a specific algebraic expression in the form $\alpha_1 o_1 \alpha_2 \dots \alpha_{n-1} o_{n-1} \alpha_n$ which configuration of brackets would maximize the value of the expression given that $\forall i \,\alpha_i \geq 1 \in \mathbb{N}$ ?

Is it sufficient to only place brackets over the $+$ series in the expression? I've checked this rule with $a_1 + a_2 \cdot a_3 $ and $a_1 + a_2 \cdot a_3 +a_4 $ but couldn't find a counter example.

Answer 1

Assuming these are positive integers, we can use a dynamic programming technique to solve this problem.

We are given a problem similar to the matrix multiplication (n matrices) problem, where one has to determine the optimal ordering of parenthesis such that the total expression is maximized - this problem is similar in structure.

1. Subproblems

Let's say we are given the expression : A[1] o A[2] o A[3] o ... o A[n]. In order to maximize the expression using dynamic programming, our guess for the solution would have to be one that maximizes the last operation (multiplication/addition) - i.e., we need to run through all combinations of parenthesis such that we find the greatest value. Particularly, we are interested in all combinations of k, such that :

(A[1] o ... o A[k]) o (A[k+1] o ... o A[n]) is maximized, which means we can choose k' such that
   /           \
  /             \
 /               \
/                 \
(A[1] o ... o A[k']) o (A[k'+1] o ... oA[k]), and so on.

We are interested in finding the optimal value of the expression A[:k] and A[k+1:], then combining them based on the operator that separates the prefix and suffix expression. As we can see from our result above, we are interested in both the prefix and suffix of the "string" A. Therefore, our subproblem is reduced to finding the optimal parenthesization of a "substring" of values A(i->j), such that

(A[i] o A[i+1] o ... o A[k]) o (A[k+1] o ... o A[j]) is maximized, where k takes values from i->j => k = O(n) (the worst case, we go through the entire list)

There are n^2 such subproblems (follows from the fact that there are Theta(n^2) substrings in a string of size n).

2.Recursive definition of optimal value

Our general recursion definition describes finding the optimal value for the expression by varying 'k' over the given substring:

optVal(i,j) = max{optVal(i,k) o optVal(k+1,j) for k:i->j}, where 'o' is the operator '+' or '*'

3. Time per subproblem

As we can see above, each subproblem finds the max val of the expression by varying k over i->j, or atmost n values.

Hence the time complexity of the subproblem is O(n).

4.Pseudocode

We have to consider two cases in the recursion :

 1. op = '+'
 2. op = '*'

So the recursion for the optimal value looks something like this :

optVal(inp){ 

if(|inp| == 1) 
  return inp[1] // base case 
else
  opt_val = 0;
  for(k=2; k<len(inp); k+=2)
    if(inp[k] == '+')
      opt_val = max{opt_val, optVal(inp[:k]) + optVal(inp[k+1:])} 
    else
      opt_val = max{opt_val, optVal(inp[:k]) * optVal(inp[k+1:])}

5.Run-time analysis

The running time of this solution can be defined as follows

T(n) = # of subproblems * time/subproblem

using our results from sections 1 and 2 above, we have

T(n) = n^2 * O(n) = O(n^3)

6. Argument for correctness

In the above problem, we can see that no matter how we parenthesize a subexpression, there has to be some final operation that is peformed. We mentioned above that the final parenthesization of A[i] o A[j] must be of the form (A[i]...A[k] ) o (A[k+1]..A[j]), for k:i->j - we observe here that no matter the choice of k, the expressions (A[i]...A[k]) and (A[k+1]...A[j]) must also be evaluated optimally. If this isn't the case, then there would exist some other optimal solution that could solve any of these given subproblems optimally - but this cannot happen, because we could maximize the expression by replacing the current subproblem solution with an optimal solution instead. We have therefore constructed the solution to this optimization problem for the general case (i,j) in terms of smaller (but still optimal) subproblem solutions. So, the final solution can be derived by maximizing the value over all the optimal solutions in the subexpression A(i,j) by letting k run from i->j.

Answer 2

Your intuition is correct and I shall prove it. $\def\nn{\mathbb{N}}$

Solution

Note that every expression corresponds to a complete binary tree (every number is a leaf node and every operation is an internal node with exactly two child nodes). We can thus define the depth of an operation to be the distance from the root node.

Start from any expression of the allowed form.

Whenever $E$ has some subexpression of the form "$( a \times b ) + c$":

  Substitute that subexpression in $E$ with "$a \times ( b + c )$".

  Then the value of $E$ is not decreased because:

    $+,\times$ on $\nn^+$ are positive and increasing in each of their inputs.

    Thus $ac \ge c$ because $a \ge 1$, and hence the substituted expression has greater value.

  Also the total depth of the multiplication operations has decreased.

We do similarly whenever $E$ has some subexpression of the form "$a + ( b \times c )$", and we repeat these two modifications on the new expression as long as they can be performed.

Eventually we must stop because the total depth of multiplication operations is an integer. At that point $E$ cannot have any multiplication that is a child node of an addition, and hence cannot have any multiplication before addition at all.

Therefore every expression has lower value than some expression that does all additions before all multiplications. It is easy to check that all such expressions have the same value, and so we have found the optimal solution.

Notes

Observe that the substitution will not work if the numbers are allowed to be zero. The optimal solution can still be described, but not so simply. Basically we first put brackets around blocks containing only multiplication and at least one zero that is not at either end (namely of the form "$a \times \cdots \times b \times 0 \times c \times \cdots \times d$"). Then we perform all additions first before all multiplications. The proof would be similar to the above.