Thread: Algorithm for determining the maximum value in an array list

1. Member
Join Date
Jun 2011
Posts
54
Rep Power
0

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:
Java 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:
Java 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?

2. Member
Join Date
Jul 2013
Posts
5
Rep Power
0

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

3. Senior Member
Join Date
Mar 2013
Location
Greece
Posts
183
Rep Power
8

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..

Java Code:
```Collections.sort(arrayList); // Sort the arraylist
arrayList.get(arrayList.size()); //gets the last item, largest for an ascending sort```

4. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

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
Last edited by jim829; 07-29-2013 at 06:20 PM.

5. Just a guy
Join Date
Jun 2013
Location
Netherlands
Posts
5,114
Rep Power
13

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?

6. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

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

7. 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:

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

Jos

8. Senior Member
Join Date
Mar 2013
Location
Greece
Posts
183
Rep Power
8

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.

9. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

Re: Algorithm for determining the maximum value in an array list

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.
...horrible way
And I said that, not Erik.

Regards,
Jim

10. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

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

11. Just a guy
Join Date
Jun 2013
Location
Netherlands
Posts
5,114
Rep Power
13

Re: Algorithm for determining the maximum value in an array list

Originally Posted by jim829
And I said that, not Erik.
I thought I was going mad!

But nope - just bald.

12. Senior Member
Join Date
Mar 2013
Location
Greece
Posts
183
Rep Power
8

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

13. Member
Join Date
Jun 2011
Posts
54
Rep Power
0

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:

Java 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! :)
Last edited by FOX427; 07-30-2013 at 09:19 PM.

14. Member
Join Date
Jun 2011
Posts
54
Rep Power
0

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???

15. Member
Join Date
Jun 2011
Posts
54
Rep Power
0

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. :)

16. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

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

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•