Find the maximum value in an array that's the sum of 3 other values

Question

Given a very large integer array, I need to find the maximum value of a4, such that:

a4 = a1 + a2 + a3

Where the ai's are all values in the array.

How would I do this?

Note: Using 4 for loops is not the ideal solution.

Answer 1

There is a simple (expected) O(n^2) solution:

1. Iterate through all pairs of array elements (a, b) and store their sum in a hash table.
2. Iterate through all candidate pairs (a4, a1) and check whether a4 - a1 is in the table. The maximum over all valid a4 is the solution. Of course you should process a4 from largest to smallest, but that doesn't affect the asymptotics.

If you want to avoid using an element more than once, you need some additional information stored in the hash table so that you can filter out pairs that colide with a1 or a4 fast.

If the integers in the array are bounded (max - min <= C), it might be useful to know that you can achieve O(n + C log C) using a discrete fourier transform (solvable using FFT).

Answer 2

First of all you should ascending sort your array. then start from the last (biggest) member of the array. For example, for [1,2,3,777,999,111,665] you'll have sortedArray = {1,2,3,111,665, 777, 999} then select 999 as a4 and try to create it with other members. So you should select as a3 and try to create (999 - 777) = 222 as a1+a2 since your array is sorted you only need to consider subarray {1,2,3,111}. if there is no pair satisfying this condition, try next biggest member (777) and retry above scenario to find the solution

Answer 3

Based on @Niklas answer, I wrote the following program in Java.

public static int sumOfThree(int [] arr) {
    int arrlen = arr.length;
    int arrijv [][] = new int [arrlen * (arrlen - 1) / 2][3];
    int arrijvlen = 0;

    quickSortInDescendingOrder(arr, 0, arrlen - 1); // sorts array into descending order

    System.out.println(Arrays.toString(arr));

    // populates array with sum of all pair values
    for (int i = 0; i < arrlen - 1; i++) {   
        for (int j = i + 1; j < arrlen; j++) {
            //  if ((arr[i] + arr[j]) < arr[0]) {       // can be added if no negative values
            arrijv[arrijvlen][0] = i;
            arrijv[arrijvlen][1] = j;
            arrijv[arrijvlen][2] = arr[i] + arr[j];
            arrijvlen++;
            //  }
        }
    }

    System.out.print('[');
    for (int i = 0; i < arrijvlen; i++) {
        System.out.print(arrijv[i][2] + " ");
    }
    System.out.print("]\n");

    // checks for a match of difference of other pair in the populated array 
    for (int i = 0; i < arrlen - 1; i++) {
        for (int j = i + 1; j < arrlen; j++) {
            int couldBeA4 = arr[i];
            if(isAvailable(arrijv, arrijvlen, couldBeA4 - arr[j], i, j)){
                System.out.println(" i3-" + j + " i4-" + i);
                return couldBeA4;
            }
        }
    }

    return -1;
}

private static boolean isAvailable(int[][] arrijv, int len, int diff, int i, int j) {
    boolean output = false;

    // returns true if the difference is matched with other combination of i,j
    for (int k = 0; k < len; k++) {
        if (arrijv[k][2] == diff) {
            int pi = arrijv[k][0];
            int pj = arrijv[k][1];

            if (pi != i && pi != j && pj != i && pj != j) {
                System.out.print("i1-" +  pj + " i2-" + pi);
                output = true;
                break;
            }
        }
    }
    return output;
}


private static void quickSortInDescendingOrder(int[] array, int low, int high) { // solely used for sorting input array into descending array
    if (low < high) {
        int partition = getPartitionIndex(array, low, high);
        quickSortInDescendingOrder(array, low, partition);
        quickSortInDescendingOrder(array, partition + 1, high);
    }
}

private static int getPartitionIndex(int[] arr, int lo, int hi) { 
    int pivot = arr[(lo + hi) / 2]; 

    while (true) {
        while (arr[lo] > pivot) {
            lo++;
        }

        while (arr[hi] < pivot) {
            hi--;
        }

        if (arr[lo] == arr[hi]) {   // can be removed if no duplicate values
            return lo;
        } else if (lo < hi) {
            int temp = arr[lo];
            arr[lo] = arr[hi];
            arr[hi] = temp;
        } else {
            return hi;
        }
    }
}

Please verify that it works and suggest for further improvements.