4
\$\begingroup\$

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?

\$\endgroup\$
11
\$\begingroup\$

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();
    
\$\endgroup\$
  • \$\begingroup\$ With the second suggested approach being the most obvious =) \$\endgroup\$ – Bogdan Alexandru Jul 12 '17 at 15:58
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Could you add a bit more context around this answer? \$\endgroup\$ – Stephen Rauch Jul 12 '17 at 15:19
  • \$\begingroup\$ @StephenRauch That is the only thing I saw. \$\endgroup\$ – paparazzo Jul 12 '17 at 15:21
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Stephen Rauch Jul 12 '17 at 16:21
  • 1
    \$\begingroup\$ @StephenRauch j = i + 1 \$\endgroup\$ – paparazzo Jul 12 '17 at 16:23

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.