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

Question

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.

Answer 1

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