Algorithm to find pair with max sum from two arrays

Question

Algorithm to find pair with max sum from two arrays

A[0 ... n] and B[0 ... n]
A[i] + B[j] = max (A[i] + B[j], with i < j) 
i,j < 99999; n < 99999

My best result is this:

int[] testArrayA = { 7, 1, 4, 5, 1};
int[] testArrayB = { 3, 2, 1, 5, 3};
String res = "";
int maxSum = 0;
for (int i = 0; i < testArrayA.length; i++)
{
 int i1 = testArrayA[i];
 for (int j = i; j < testArrayB.length; j++)
 {
 int j1 = testArrayB[j];
 if((j1 + i1) > maxSum)
 {
 maxSum = j1 + i1;
 res = i + " " + j;
 }
 }
}
System.out.println(res);

Expected answer "0 3" Current complexity \$O(n^2)\$ I think it must be much lower. Can we do it better?

• Mast: Yes, this can be done a lot faster. Welcome to Code Review! One of the Java guys will probably tell you exactly what's wrong with this.

Answer 1

We can solve this in \$O(n)\$ time. The best possible sum for a particular index, \$i\,ドル is \$S[i] = A[i] + \max(B[i+1:])\$ (using the Python notion of slice). We can update both incrementally by counting from the back, so we have to keep track of two things: \$\max(S[i:])\$ and \$\max(B[i+1:])\$.

So for the test arrays:

int[] testArrayA = { 7, 1, 4, 5, 1};
int[] testArrayB = { 3, 2, 1, 5, 3};
 ↑
 starting i

At i==3, we start with maxS == 8 and maxB == 3, since those are the only two options. With i==2, we update maxB = max(maxB, B[i+1]) = 5 and maxS = max(maxS, A[i] + maxB) = max(8, 4+5) = 9. etc.

In code:

public static void printMaxIncreasingIndexSum(int[] A, int[] B)
{
 int bIdx = B.length - 1;
 int aIdx = A.length - 2;
 int maxB = bIdx;
 int maxS = A[A.length - 2] + B[maxB];
 for (int i = A.length - 3; i >= 0; --i) {
 if (B[i+1] > B[maxB]) {
 maxB = i+1;
 }
 if (A[i] + B[maxB] > maxS) {
 maxS = A[i] + B[maxB];
 aIdx = i;
 bIdx = maxB;
 }
 }
 System.out.printf("%d %d", aIdx, bIdx);
}