# Finding the maximum sum of any 2 elements in an array of integers

this no-brainer came up to me in a technical interview. I played it safe and wrote this.

 public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

System.out.println("enter size of the array: ");

if (!in.hasNextInt()) {
System.out.println("put an integer! ");
}
int size = in.nextInt();

System.out.println("enter numbers for array");

int[] array = new int[size];

for (int i = 0; i < array.length; i++) {
array[i] = in.nextInt();
}

maxSum(array);

System.out.println(maxSum(array));
}

private static int maxSum(int[] array) {

int max = array[0];

for (int i = 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j++) {

int currentMax = array[i] + array[j];

if (currentMax > max) {
max = currentMax;
}
}
}

return max;
}
}


obviously O(n^2) is not the best approach but I just wanted to finish the question without spending to much time, what do you think?

Your code tries all $n (n+1)/2$ combinations of array elements to find the combination with the largest sum, so the complexity is $O(n^2)$.

A better solution would be to find the two largest elements in the array, since adding those obviously gives the largest sum.

Possible approaches are:

• Sort the array elements in increasing order and add the last two elements. Efficient sorting algorithms (such as Quicksort) have an average complexity of $O(n \log(n))$.
• Traverse the array once and keep track of the largest and second largest element encountered so far. Then add those elements. The complexity is $O(n)$.

Other remarks:

• Your main program computes maxSum(array) twice, which is not necessary.
• You should check if the user entered at least 2 elements, otherwise the problem is ill-defined.
• The if (!in.hasNextInt()) check is not really helpful. If the user enters a non-integer, "put an integer! " is printed, but then in.nextInt() fails with an exception. You could for example skip the entire input line until a valid integer is entered:

while (!in.hasNextInt()) {
System.out.println("Enter an integer! ");
in.nextLine();
}
int size = in.nextInt();

• With the second suggested approach being the most obvious =) – Bogdan Alexandru Jul 12 '17 at 15:58

### Overflow issues

If the largest two integers added together exceed the maximum integer value, you will not come up with the correct answer. For example, 2000000000 + 2000000000 becomes some negative value and you would miss that as the answer. To do this correctly you should do the addition using long and store the max value in a long as well:

    long currentMax = (long) array[i] + (long) array[j];


Even if you used the better algorithm of finding the two largest values in the array, you would still need to return a long in order to return the correct sum.

Should be i < array.length - 1; because j = i + 1;

This can be done in one pass. Just have an array of 2 that you save the biggest 2.

• Could you add a bit more context around this answer? – Stephen Rauch Jul 12 '17 at 15:19
• @StephenRauch That is the only thing I saw. – paparazzo Jul 12 '17 at 15:21
• I wasn't asking for you to make more points, I was just hoping for some explanation of these two points. You have added some more on the second point, which helps, but the first remains unexplained. Thanks. – Stephen Rauch Jul 12 '17 at 16:21
• @StephenRauch j = i + 1 – paparazzo Jul 12 '17 at 16:23