We are given an arithmetic expressionx1o1x2o2...xn−1on−1xn such thatxifor 1≤i≤narepositive numbers andoi∈{+,×}for 1≤i≤n−1 are arithmetic operations (summation ormultiplication). We would like to parenthesize the expression in a such a way that the valueof the expression is maximized. For example, if the expression is 3 + 4×2 + 6×0.5, then theoptimal parenthesization is (3 + 4)×(2 + (6×0.5)), with a value of 35.