CMI2010 - 6

Question

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.

Comments

I have done the solution below. Check it tell me if anything is wrong.

---

I think the answer is correct THANK YOU

---

https://gateoverflow.in/215034/cmi2010-6

Answer 1

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

Comments

@Shaik Masthan

check original answer, it is written there

---

@Debargha Bhattacharj

will it be 353 or 357??

and in table in place of 2nd 9, it will be 10.

---

@srestha

Thanks for pointing out the mistake. The correct answer will be 352 (same as the original answer given by @Kushagra Chatterjee).

 

@Shaik Masthan

I think the time complexity will be- $O(mn^2) \\ \text { where } m = \text { no. of elements in List B, } n = \text { no. of elements in List A }$