edited by
2,253 views
6 votes
6 votes

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.

edited by

1 Answer

10 votes
10 votes

Solution

CORRECTION :- The time complexity required for to do the algorithm below will be O($n^2$)

Related questions