MHB Maximize Expression Result: Algorithm & Tips

[evinda]

Hello! (Wave)

I want to write an algorithm that runs in polynomial time and finds the best way to put parenthesis at a given expression so that the result of the operations is maximized.
The input of the algorithm should be a sequence $a_0, b_0, a_1, b_1, \dots, a_{m-1}, b_{m-1}, a_m$, where $a_0, a_1, \dots, a_m$ are real numbers and $b_0, b_1, \dots, b_{m-1}$ are operators and could be either plus or minus.

Could you give me a hint what we could do in order to find the right order of the parenthesis so that the result of operations of the given expression is maximized? (Thinking)

 

[Evgeny.Makarov]

I don't have a complete solution, but the problem seems to be similar to the Matrix chain multiplication problem.