1

Which is better to use for an array of millions of integers(ages)

public static int findMax(int[] x) {
    int max = 0;
    int curr = 0;
    for (int a : x) {
        curr = Math.max(curr, a);
        max = Math.max(max, curr);
    }
    return max;
}
public static int findMax(int[] x){
    List<Integer> list = new ArrayList<>();
    for (int y : x){
        list.add(y);
    }
    return Collections.max(list);
}
EastXWest
  • 13
  • 5

2 Answers2

4

The first one will definitely be faster than the second one, as you really don't want to be making an arraylist for no reason just to find the maximum of an array!

Also, there is no reason to use two different variables for the current and the max, just the max will suffice, like so: 

public static int findMax(int[] x) {
  int max = Integer.MIN_VALUE;
  for (int a : x) {
      max = Math.max(max, a);
  }
  return max;
}

Note: I used the minimum integer because the largest value in your array may be negative. Also, you could just use an if-condition instead of Math.max(), but it'll work either way. This also saves you an extra operation. The runtime is O(n) in every case.

Lavaman65
  • 863
  • 1
  • 12
  • 22
  • Perfect, i especially like the generalization of the solution. Thank you, i just used it to efficiently find the min as well – EastXWest Jul 25 '17 at 20:20
  • @EastXWest If you're looking for a practical way to find the maximum then you'd have to consider parallel algorithms. If you're looking for theoretical solutions this is fine. – user1803551 Jul 25 '17 at 20:34
  • @EastXWest It's a huge topic with tons of resources. Have a quick read at [Wikipedia](https://en.wikipedia.org/wiki/Parallel_algorithm). Since almost all CPUs today have more than 1 physical core, you can leverage this to run an algorithm on multiple cores at once, which will be much faster. The simplest example would be to split the array into 2, have each core run the sequential algorithm and then combine the results. That's about twice as fast obviously. Java also has built in implementations a la [fork-join](https://en.wikipedia.org/wiki/Fork–join_model). – user1803551 Jul 25 '17 at 20:43
  • Thanks @user1803551, i have found it, i was a bit out of it i see what you mean now. I am grateful. Do't know why i didn't consider this. Appreciated – EastXWest Jul 25 '17 at 20:50
0

They both look like they are O(n). You could always use a logger and see what the time is. The following is a link that talks about logging time executed: How do I time a method's execution in Java?

Scott Blanch
  • 178
  • 1
  • 8