Maximum sum of pairwise absolute difference of values in multiple arrays and index

user_11506111 0
Viewed 306

Suppose we have 5 arrays A, B, C, D, E each of size N. Now we need to find the

max(|A[i] - A[j]| + |B[i] - B[j]| + |C[i] - C[j]| + |D[i] - D[j]| + |E[i] - E[j]| + |i - j|)       where 1<=i<j<=N.

I'm well aware of the problem to find max(|A[i] - A[j]| + |i - j|) for a single array in O(n). But its solution method doesn't seem to be applicable in this case.

So my question is how to solve this problem in O(nlogn) runtime or if possible O(n) runtime.

algorithm
1 Answers

kraskevich's answer for the 2D case generalizes to d dimensions, with running time O(2d d n). With d = 6, this is O(n). For each of the 2d d-dimensional vectors c with ±1 coordinates, we find the input vector v that maximizes the dot product c⋅v. For each of these vectors v, we evaluate the objective when they are paired with each vector w.

user_21446690
Related