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?

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