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.

CodePudding user response：

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

CodePudding user response：

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.