I have the following problem: Given a set of $n$ values, $x_1,...,x_n$, and $n-1$ operators between them (that is, we are given the formula $x_1 o_1 x_2 o_2 ... o_{n-1}x_n$), our objective function is to place braces in some places to maximize the value.
All the values are positive (but some $x$s may be smaller than 1), and we are supposed to solve the problem using dynamic programming. I came up with a solution, and of course it is depends both on the operator $o_j$ and the value after it, $x_j$.
Now, I want to write the recursive function, but I am struggling with the formalities - at stage $j$, given a set of operations and $x$s, we are trying to maximize the following by placing brackets. $$f = \max \{ \{x_1,o_1,...,o_{j-1},x_j \} \}$$
How should I express the fact that we are only placing brackets, what we max over? What would be argmax?
For example, if we have $(x_1,x_2,x_3) = (1,2,3) and (o_1, o_2) = (+,\times)$, then the max would be given by $(1+2)\times3$.
Thanks!
