Maximum average distance between two numbers across multiple arrays

After a linear-time transformation indexing the numbers, this problem boils down to computing the diameter of a set of points with respect to L1 distance. Unfortunately this problem is subject to the curse of dimensionality.

Given

    1 2 3 4
1: [1,4,2,3]
2: [4,2,3,1]
3: [2,3,4,1]

we compute

    1 2 3
1: [1,4,4]
2: [3,2,1]
3: [4,3,2]
4: [2,1,3]

and then the L1 distance between 1 and 2 is |1-3| + |4-2| + |4-1| = 8, which is their average distance (in problem terms) times k = 3.

That being said, you can apply an approximate nearest neighbor algorithm using the input above as the database and the image of each point in the database under N+1-v as a query.