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).