CODEWITHSUNDEEP
algorithm
dpsthree
dpsthree

Reputation: 2285

Algorithm for maximizing the product of powers

Given two arrays of integers, B and A, how can we rearrange their elements such that ∏ A[i]B[i] for all i is maximized?

Upvotes: 3

Views: 1062

Answers (3)

user127.0.0.1
user127.0.0.1

Reputation: 1337

Assuming array has postive integers,

If you take the log of the product:

It becomes Sum B[i]* log A[i]

Now this can be maximized if both are arranged in ascending order, because of the rearrangement inequality, (see here: http://en.wikipedia.org/wiki/Rearrangement_inequality) and log being an increasing function.

So, sort A in ascending, sort B in ascending and you are done.

Upvotes: 2

Antti Huima
Antti Huima

Reputation: 25542

If the arrays contain non-negative numbers, you just sort both A and B in descending order. To see that this gives the maximum product, consider that once A and B are sorted in this order, you can try to swap two items of A, say A[i] and A[j] s.t. i 

              B[j]      B[i]
          A[i]      A[j]
          ------------------
              B[i]      B[j]
          A[i]      A[j]

i.e. A[i]B[j]-B[i] A[j]B[i]-B[j], which equals (A[i]/A[j])(B[j]-B[i]) where the exponent is zero or negative because B[i] ≥ B[j]. By assumption A[i] ≥ A[j] so A[i]/A[j] ≥ 1. Therefore the ratio is 1 or less as the exponent is either 0 or negative. This shows that the new product is smaller in value than the old product. Note: this is just an illustration, not a formal proof because it considers only the swapping of two elements.

Upvotes: 2

cohensh
cohensh

Reputation: 482

Assuming non-negative, it seems like you should just sort them both in increasing or decreasing (but the same) order.

Since everything is multiplied, you'll end up with A[0] * A[0]* ... * A[0] * A[1] *.. * A[1] *... etc.

With B[0] number of A[0]'s and B[1] number of A[1]'s, therefore, if you assume A[0] is the largest number, you want the most of them, so you should have the largest value B in B[0], and then you want the second most in B[1], etc.

If you can have negative numbers in A but not B then this still gives you the largest absolute value but the sign could be negative.

Upvotes: 3

Related Questions