+1 vote
64 views

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 | 64 views
0
I think the answer should be O(n log^k (n))
0
WHY!!!
0
the bracketing done in example is only applicable in that example right?
0
In the example they are showing how to bracket the elements of the first list.

Suppose the first list is {1,2,3,4,5} and the second list is {+,*,+}

Then one expression will be 1+(2*(3+4))

I hope this helps.
0
I have done the solution below. Check it tell me if anything is wrong.
0
I think the answer is correct THANK YOU

+1 vote
Suppose the first list has $m$ numbers and the second list has $n$ operators, here ($m>n$).

So, at each expression we will have $(n+1)$ numbers.

Note that maximum value of the expression occurs when $(n+1)$ maximum numbers out of $m$ numbers in the first list will be present in the expression.

So, our goal is to find $(n+1)$ maximum numbers out of $m$ numbers in the first list.

Now, finding the maximum number out of $m$ numbers in the first list can be done in $O(n)$ time.

Build a max heap and extract the root node. Building a max heap takes $O(n)$ time.

Now, the remaining $n$ maximum numbers can be determined in $O(log n)$ time. (Call max-heapify on the max-heap and delete the root node).

Note that here $n$ is a constant number of operators in the second list.

So, to find $(n+1)$ maximum numbers out of $m$ numbers in the first list can be done in $n + O(log n)$ time.

So, to determine the maximum value among all the expressions can be done in $n + O(log n)$ time..