The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+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

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

+1 vote

+1

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.

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.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,713 questions

46,750 answers

140,552 comments

58,380 users