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.
Question is too much old but I think still keeps value. Here is a simple Python program to do this.
def maximize_difference(arr): n = len(arr) max_diff = float('-inf')
for i in range(n):
for j in range(i + 2, n):
for k in range(j + 2, n):
for l in range(k + 2, n):
diff = (arr[i] * arr[j]) - (arr[k] * arr[l])
max_diff = max(max_diff, diff)
return max_diff
arr = [2, 1, 3, 4, 8, 6, 7, 9] result = maximize_difference(arr) print(result)
Thanks
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.
thanks for the soln
arun203301 last updated on Oct. 8, 2021, 12:55 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.