Efficiently sum max(Ai+Bj, Bi+Aj) over all i, j

user_13946224 0
Viewed 1424

You are given two integer arrays A and B of length N. You have to find the value of two summation:

Z=Σ Σ max(Ai+Bj, Bi+Aj)

Here is my brute force algorithm

  1. for loop (i to length)
  2. for loop (j to length)
  3. sum+=Math.max(A[i]+B[j], A[j]+B[i]);

Please tell me a better efficient algorithm for this.

array-algorithms data-structures algorithm
2 Answers

Rewrite the sum as Z = Σi Σj [max(Ai−Bi, Aj−Bj) + Bi + Bj] by using the distributive property of plus over max. Then construct C = A−B, sort it, and return Σi (2i+1)Ci + 2n Σi Bi (using zero-based indexing).

user_21446690

A minor improvement I can think of is to omit the results that you already computed. This means, instead of beginning the inner loop from 0, you can start with j = i. Since you already have computed the results for j < i in the previous loops. To achieve this, you can change the instruction in the inner loop to the following:

if i != j
     sum += 2 * Math.max(A[i]+B[j], A[j]+B[i]);
else
     sum += Math.max(A[i]+B[j], A[j]+B[i]);

The reason is that every pair of i and j are visited twice by the loops.

user_64094580
Related