Can you help me with the algorithm:
Given 2 arrays of equal size a[] and b[] with integer numbers greater or equal to 1.
Find non-equal indices i and j (i != j) such that the value -
max(a[i]*b[i] + a[i] * b[j] + a[j] * b[j], a[i]*b[i] + a[j] * b[i] + a[j] * b[j])
will be maximum.
Example:
a = [1, 9, 6, 6] and b = [9, 1, 6, 6].
Maximum will be at i = 2 and j = 3 (zero-based indexing):
a[2]*b[2] + a[2]*b[3] + a[3] * b[3] = 6*6+6*6+6*6 = 108
Is there a way to find i and j in less then quadratic time? And the same question for finding objective function value in less then quadratic time?
Thank you!
Yes, there’s an O(n log n)-time algorithm.
If we look at the function f(x) = max {a[i] b[i] + a[i] x | i}, it traces out a lower (convex) hull. It basically suffices to evaluate f(b[j]) + a[j] b[j] for every j, with the one sticking point that we need i ≠ j.
To fix that problem, we turn to an incremental hull algorithm with amortized O(log n)-time insertions. The canonical algorithm keeps the hull in sorted order, allowing for O(log n)-time queries. Starting with an empty hull, for each index i, we query i and then insert i. Do this once in forward order and once in reverse order, and take the max.