Dynamic programming: maximize value of arithmetic expression using parenthesis
algorithm, dynamic-programming
Solution
I think the same relation to the matrix multiplication algorithm will work.
The function we are trying to compute is
F(i,j) = maximum number that can be computed using Xi ... Xj
The base case is when we have a single number:
F(i,i) = Xi
And the recursive case is for operations between two subexpressions wrapped in parenthesis:
F(i,j) = for k = i,j-1, maximize
F(i,k) Yk F(k+1, j)
I think greedly maximizing the numbers should work because for multiplication and addition over positive numbers, we want both the operands to be as big as possible.
If we allow division, then we will want the second operand to be as small as possible to maximize the result. In that case, instead of just computing `F`, you will also need to compute a similar `G` that minimizes the value over the interval.
If we allow subtraction, then we will need to account for positive vs negative numbersd. If you keep track of largets positive, smallest positive, largest negative and smallest negative I think you should be able to get any values you need. Perhaps there is an alternative that requires less computation though.
I didn't stop to think about the implications of `%`. For starters, how does it behave with the non-integer results from `/`?
Problem
This is an interview question asked to me sometime back: Suppose you are given an expression E= x1 y1 x2 y2....yn-1 xn. Where Xi belong to natural number and Yi belongs to { +,*} you need to parenthesize such that it maximize the value of E ? I was able to think in the direction of Dynamic Programming and could related it to matrix chain multiplication problem, but was stuck on deriving the exact recursive relation for this one. Moreover, follow-up questions just complicated the situation for me: Let's change Yi to { +,-,*,/}, then how to maximize E? Now add % operator in that set..then how to maximize E? An explanation on to how to approach and build a solution for this would be great.