You are given a list of positive integers along with a sequence of operations from the set $\left \{ *,+\right \}$ .You construct expressions from these two lists so that:
- The numbers in the expression are drawn from the first list, without repetition and without altering their order.
- All the operators in the second list are used in the expression, in the same order.
For example, if the two lists are $[1,3,2,1,4]$ and $[′∗′,′+′]$ the set of possible expressions you can form are
$1∗3+2,1∗3+1,1∗3+4,1∗2+1,1∗2+4,\ldots,2∗1+4,1∗3+2,1∗3+1,1∗3+4,1∗2+1,1∗2+4,\ldots,2∗1+4$
For each expression, the value is computed by bracketing operators from the right. That is, the expressions above are evaluated as
$1∗(3+2), 1∗(3+1), 1∗(3+4), 1∗(2+1), 1∗(2+4),…,2∗(1+4), 1∗(3+2), 1∗(3+1), 1∗(3+4), 1∗(2+1), 1∗(2+4),…,2∗(1+4)$
The aim is to determine maximum value among these expressions. In this example, the maximum value is $18$, from the expression $3*2+4,$ which is evaluated as $3∗(2+4) = 3*6 =18$.
You may assume that the length of the first list is more than the length of the second list.
Describe an algorithm to solve this problem.