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

Question

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?

Answer 1

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

• Bogdan Alexandru: With the second suggested approach being the most obvious =)

Answer 2

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.

Answer 3

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.

• Stephen Rauch: Could you add a bit more context around this answer?
• paparazzo: @StephenRauch That is the only thing I saw.
• Stephen Rauch: 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.
• paparazzo: @StephenRauch j = i + 1