Problem $3$

We are given an arithmetic formula consisting of nonnegative integers alternating with op$-$

erators, where the allowed operators are $+$ and $**.$ For example:

$2**3+0**6**12+4**2$

We can change the value of such a formula by introducing parentheses. For example:

$2**(3+(0**(6**(12+(4**2)))))=6$

$(((2**3)+0)**6)**((12+4)**2)=1152$

Give an algorithm to find the maximum value of that parenthesization of the given arithmetic

formula can yield. Your algorithm should work in $O(n^3),$ although faster is better. Note

that the arithmetic formula given as an input does not contain any parentheses; you may

assume the integers in the formula are $s_1,s_2,$dots,$s_n($from left to right$)$ and the operators are

$o_1,o_2,$dots,$o_{n-1}($also from left to right$).$