The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

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 
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.

asked in Algorithms by (417 points)
edited by | 64 views
I think the answer should be O(n log^k (n))
the bracketing done in example is only applicable in that example right?
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.
I have done the solution below. Check it tell me if anything is wrong.
I think the answer is correct THANK YOU

1 Answer

+1 vote
Best answer
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..
answered by Loyal (8.2k points)
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,117 questions
44,700 answers
43,761 users