Solution: Maximum Value of an Arithmetic Expression

Solution

Each of the five operations in the expression

$$(5−8+7×4−8+9)$$

can be the last (or the outermost) one. Consider the case where the last one is “$×$” (that is, multiplication). In this case, we need to parenthesize two subexpressions

$$(5−8+7) ~~\text{and}~~ (4−8+9)$$

so that the product of their values is maximized. To find this out, we find the minimum and maximum values of these two subexpressions:

$$\begin{aligned}min(5−8+7)&=(5−(8+7))= −10,\\ max(5−8+7)&=((5−8)+7)= 4,\\ min(4−8+9)&=(4−(8+9))= −13,\\ max(4−8+9)&=((4−8)+9)= 5. \end{aligned}$$

From these values, we conclude that the maximum value of the product is $130$.

Assume that the input dataset is of the form

$$d_0~~ op_0~~ d_1~~ op_1~~ \cdots~~ op_{n−1}~~ d_n,$$

where each $d_i$ is a digit and each $op_j ∈ \{+, −, ×\}$ is an arithmetic operation. The discussion above suggests that we compute the minimum value and the maximum value of each subexpression of the form

$$E_{l,r} = d_l~~ op_l~~ d_{l+1} ~~ op_{l+1} ~~ \cdots~~ op_{r−1}~~ d_r ,$$

where $0 ≤ l ≤ r ≤ n$. Let $minValue(l,r)$ and $maxValue(l,r)$ be, respectively, the minimum value and the maximum value of $E_{l,r}$. Then,

$$minValue(l,r) = \min_{l \leq m < r} \begin{cases} minValue(l,m)~~ ~~ op_m ~~ ~~ minValue(m+1,r) \\ maxValue(l,m)~~ ~~ op_m ~~ ~~ minValue(m+1,r) \\ maxValue(l,m)~~ ~~ op_m ~~ ~~ minValue(m+1,r) \\ maxValue(l,m)~~ ~~ op_m ~~ ~~ maxValue(m+1,r) \end{cases}$$

$$maxValue(l,r) = \max_{l \leq m < r} \begin{cases} minValue(l,m)~~ ~~ op_m ~~ ~~ minValue(m+1,r) \\ maxValue(l,m)~~ ~~ op_m ~~ ~~ minValue(m+1,r) \\ maxValue(l,m)~~ ~~ op_m ~~ ~~ minValue(m+1,r) \\ maxValue(l,m)~~ ~~ op_m ~~ ~~ maxValue(m+1,r) \end{cases}$$

The base case is $l = r$:

$$minValue(l,l) = maxValue(l,l) = dl .$$

These two recurrence relations allow us to compute the optimal values for $E_{l,r}$ by going through all possibilities of breaking $E_{l,r}$ into two subexpressions $E_{l,m}$ and $E_{m+1,r}$.

Another way of looking at the resulting recurrence relation is the following. A natural way to visualize a particular parenthesizing is to represent it as a binary tree: