# Algorithm for determining the maximum value in an array list

• 07-28-2013, 11:54 PM
FOX427
Algorithm for determining the maximum value in an array list
Hi All! i am doing review exercises from Java book, basically here is a given code for optimal solution in the book:
Code:

```public BankAccount5 getMaximum()   {       if (accounts.size() == 0) return null;       BankAccount5 largestYet = accounts.get(0);       for (int i = 1; i < accounts.size(); i++)       {         BankAccount5 a = accounts.get(i);         if (a.getBalance() > largestYet.getBalance())             largestYet = a;       }       return largestYet;```
now i need to use alternative approach by initializing largestYet with null and go through every element in the list, then compare both methods, so far I am here:
Code:

```public BankAccount5 getMaximum2()   {           if (accounts.size() == 0) return null;           BankAccount5 largestYet = null;           for (int i = 0; i < accounts.size(); i++)           {                   BankAccount5 element = accounts.get(i);                   if(.........)                           largestYet = element;                             }           return largestYet;   }```
can some1 give me a hint how to implement if statement so I could finish this code?
• 07-29-2013, 12:57 AM
AlexHail
Re: Algorithm for determining the maximum value in an array list

Since largestYet is set to null you really cant compare it to anything because there is nothing to compare... so when checking all the balances, put the first value you find into a variable. Then check all the other balances in your list against that first variable, set the largest of them to your largestYet and return.

Let me know if you have any questions, post progress
• 07-29-2013, 04:56 PM
Re: Algorithm for determining the maximum value in an array list
The best Way to find the Max of an ArrayList is to use Sort().. just sort the arrayList and get the first or the last item..

Code:

```Collections.sort(arrayList); // Sort the arraylist arrayList.get(arrayList.size()); //gets the last item, largest for an ascending sort```
• 07-29-2013, 05:18 PM
jim829
Re: Algorithm for determining the maximum value in an array list
That is a horrible way to get the maximum value because even the best sorting algorithm, on average, is worse than O(n) in efficiency.

A better way is to assign the first value in the list to some variable max. Then iterate over the list starting with the next value and just doing a simple compare, replacing max with the current value depending on the outcome of the comparison.

Regards,
Jim
• 07-29-2013, 05:25 PM
gimbal2
Re: Algorithm for determining the maximum value in an array list
I agree with you in general, but I do want to note that performance should not be a definitive reason to choose to not do something. Yes a sort is slow but a sort on a small collection is still fast, so if it is simple code to sort and get the last element to get what you want, why not?
• 07-29-2013, 05:34 PM
jim829
Re: Algorithm for determining the maximum value in an array list
You've got a valid point. And if the desire was to obtain something for which writing an efficient routine would be very time consuming as opposed to using a combination of the available classes in the JDK API I would be all for it. But finding a maximum value in a list or array is trivial. And I also took issue with someone saying that using a sort is the "best way." If the poster had said that using a sort was a more convenient way of doing it then the efficiency issue would not have entered into the picture.

Regards,
Jim
• 07-29-2013, 05:54 PM
JosAH
Re: Algorithm for determining the maximum value in an array list
If that 'largestYet' element is set to null, the expression in the if-clause can be:

Code:

```if (largestYet == null || largestYet.compareTo(element) < 0)   largestYet= element;```
kind regards,

Jos
• 07-29-2013, 11:06 PM
Re: Algorithm for determining the maximum value in an array list
gimbal2 really, the sort way isn't better than comparing each item again and again..?? hmmm interesting..
i believed that using sort method makes the code more clear and not necessary faster but more good looking..
hmm horrible way ... hmm thx for info.. i didn't know that.
• 07-30-2013, 12:32 AM
jim829
Re: Algorithm for determining the maximum value in an array list
Quote:

the sort way isn't better than comparing each item again and again..?? hmmm interesting.

How do you think you can do a sort without comparing items? Usually, sorting algorithms do more than a single pass thru the array. I woud also say that they are more computationally intensive than just finding a maximum value of a list.
Quote:

...horrible way
And I said that, not Erik.

Regards,
Jim
• 07-30-2013, 02:48 PM
jim829
Re: Algorithm for determining the maximum value in an array list
After rethinking this I believe my use of the word "horrible" to describe the process was a poor choice. Although I clearly do not believe using sort is the most efficient method the one you posted certainly works in a pinch and may be more convenient. Ironically, several days before your post I had read the article Erik (gimbal2) had posted. It was very enlightening and goes to the point of his comments on your method. I post it again for reference. It was also very enlightening to learn that in certain situations the Java compiler uses StringBuilder to optimize concatenation of String objects.

Regards,
Jim

The Developer Insight Series, Part 1: Write Dumb Code -- Advice From Four Leading Java Developers
• 07-30-2013, 03:47 PM
gimbal2
Re: Algorithm for determining the maximum value in an array list
Quote:

Originally Posted by jim829
And I said that, not Erik.

I thought I was going mad!

But nope - just bald.
• 07-30-2013, 07:45 PM
Re: Algorithm for determining the maximum value in an array list
Thx for the informations.. i must change a lot of things in my codes :P
• 07-30-2013, 08:16 PM
FOX427
Re: Algorithm for determining the maximum value in an array list
to AlexHail
But isn't it the same as first approach that is listed above? I forgot to mention that book says we need to test whether largestYet is still null. here is what I have now:

Code:

```public BankAccount5 getMaximum2()   {       if (accounts.size() == 0) return null;       BankAccount5 largestYet = null;       for (int i = 0; i < accounts.size(); i++)       {           BankAccount5 element = accounts.get(i);           if(largestYet==null || largestYet.getBalance() < element.getBalance())               largestYet = element;                   }       return largestYet;   }```
it seems to be working fine...of course second approach seems to be less efficient as we need to redundant checks every time iteration happens...Thank you for your willingness to help! :)
• 07-30-2013, 08:29 PM
FOX427
Re: Algorithm for determining the maximum value in an array list
Jos, I did something similar:
public BankAccount5 getMaximum2()
{
if (accounts.size() == 0) return null;
BankAccount5 largestYet = null;
for (int i = 0; i < accounts.size(); i++)
{
BankAccount5 element = accounts.get(i);
if(largestYet==null || largestYet.getBalance() < element.getBalance())
largestYet = element;

}
return largestYet;
}
but I always thought that you can use compareTo method only with strings???
• 07-30-2013, 08:33 PM
FOX427
Re: Algorithm for determining the maximum value in an array list
Thank you very much to everyone! I didn't expect that a lot of people will discuss this small exercise review. Appreciate. :)
• 07-30-2013, 08:48 PM
jim829
Re: Algorithm for determining the maximum value in an array list
Actually, I just noticed something. It appears that since the bank account objects are stored in a List then the objects must implement the Comparable interface or a Comparator will need to be passed using a different method call. Otherwise, the Collections.sort() method will generate a compile-time error.

Regards,
Jim