# Solution: Maximum Value of an Arithmetic Expression

Solution for the Maximum Value of an Arithmetic Expression Problem.

We'll cover the following

## 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:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.