The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+5 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 
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 (305 points)
edited by | 500 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

+9 votes


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

answered by Loyal (9.5k points)
edited by
You are not taking into account that the numbers from the list should be in the same order, in that case max heap won't work out as it changes the order.

Your algorithm is wrong ,

Let's take an example : Numbers list 2,3,1,4 and operator sequence *,+. In this case the maximum value possible is 3*(1+4)=15 and this does not use the 3 largest number so clearly your solution is wrong.

@Arjun Suresh please the change the accepted answer to not accepted.
Vinay thanks a lot for pointing out my mistake. Without it I would be happy with my wrong explanation. I have edited my answer can u please check it once more and tell me whether I am wrong or not.

Nice explaination @Kushagra

According to me, here computing the list A1 should take O(n2) time (since we're comparing the sum of every element of list A every element having index greater than it). Similarly for A2, A3, A4 also (since the question says we can assume that the length of the first list is more than the length of the second list).

Correct me if i am wrong.

what is the correct answer?  can someone please tell.
The above answer is correct except the time complexity should be O(n^2 k). As pointed by @Nirmal in the previous comment
You have assumed that list B contains,

+ , * , * ,+  as operators. But it is given that list B is a set. So it cant have repetitions.

Am I right?
neither of the lists are sets look at the 1st list of the example given by the question setter [1,3,2,1,4]  1 is repeated in it

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
49,814 questions
54,518 answers
75,287 users