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