# Algorithm to find pair with max sum from two arrays

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?

• 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. – Mast Dec 9 '15 at 20:34

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);
}