< Back to forum

Array Problem

I am not able to solve it please help. Thanks in advance

Given an array with min length of 8, choose 2 groups of 2 numbers such that in each group, the two numbers must not be adjacent. Multiply the numbers in both groups and subtract one from other. Maximize this result Ex: 2,1,3,4,8,6,7,9 2 groups -> 1,4 & 6,9 -> Diff = 54-4 = 50

Asked by: iammafia on Aug. 21, 2021, 10:35 p.m. Last updated on Aug. 21, 2021, 10:35 p.m.


The example you gave has maximum result 66. Which can be achieved by picking {2,3} and {8,9}.

mahawarvishal10 last updated on Aug. 27, 2021, 6:47 p.m.

Enter your answer details below:


Preview

Enter your comment details below:

Preview




1 Answer(s)

avatar

First, we must set up a rule that no two adjacent elements can be multiplied with each other.

Next, we'll have to find a partition of this array and pick the maximum product in one partition and minimum product in the other. Considering the elements of this array are positive, smaller elements multiply to give smaller products and larger ones give a larger product.
For each index i in this array, calculate four values.
1) Maximum product of any two elements on the left of i (inclusive).
2) Minimum product of the same as mentioned in 1).
3) Maximum product of any two elements on the right of i (inclusive).
4) Minimum product of the same as mentioned in 3).

You might be able to see that calculating these products is easy dynamic programming. I'll demonstrate the first one.
First P[i] = P[i-1]. Because the elements on the left of i-1 are also at the left of i.
Then P[i] = max(P[i],A[i]*max_element(0,i-2)). Here max_element(l,r) denotes the maximum element in the range from l to r in the array. You can calculate this element while traversing the array. We need this element because only the maximum element will give the maximum product. And this element should lie at index <=i-2.

Once you understand this, it's easy to build the array for remaining 3 cases. For minimum product, it'll be min_element and for the right of i, take values from P[i+1].
Once we get the values, we need fix an index i such that the two pairs we want to pick, one of them belongs to the left of i (inclusive) and other from the other half of the array. And the answer for that particular partition is max(maxOnLeft-minOnRight, maxOnRight-minOnLeft). And the overall answer is the maxima of this one over all partitions.

For implementation details please reply.

mahawarvishal10 last updated on Aug. 27, 2021, 6:37 p.m. 0    Reply    Upvote   

avatar

Solution.

mahawarvishal10 last updated on Aug. 27, 2021, 6:48 p.m.

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.