8
\$\begingroup\$

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?

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

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);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.