Java Notes

Array Example - Maximum

To find the maximum value in an array:

Assign the first (or any) array element to the variable that will hold the maximum value.
Loop through the remaining array elements, starting at the second element (subscript 1). When a larger value is found, that becomes the new maximum.

//===================================================== max
public static int max(int[] t) {
    int maximum = t[0];   // start with the first value
    for (int i=1; i<t.length; i++) {
        if (t[i] > maximum) {
            maximum = t[i];   // new maximum
        }
    }
    return maximum;
}//end method max

To make this work with object types (eg String), you will have to change the type declarations of course, but you will also have to change the comparison to use .compareTo(), which must be defined for that object type.

The minimum can be found by the same algorithm, simply inverting the test. It's also easy to add a test for the minimum to this loop so that both the maximum and minimum are determined within the same loop.

There is one common variation on this -- sometimes it isn't the maximum value that is desired, but the index of the maximum value (eg, so it can be changed).

Common error -- starting with the wrong initial value

Choosing the first value of an array for the maximum (or minimum) always works. However, most student programs start with a fixed value, like zero. This often appears to work because most test data values are positive. However, it's very fragile, and often wrong. If you really need to start with an initial value in some situation (unlikely), then use the smallest possible value, Integer.MIN_VALUE as the initial value for the maximum.

Non-full arrays - need additional parameter

This method assumes that all the elements of the array should be sorted. When your arrays may not be full (a common situation), the method should have an additional parameter which is the number of elements currently in it. See the programming exercises below.

Error possibility - no elements

A minor problem with this algorithm is what to do if there are absolutely no elements in the array -- t.length is zero. There is no maximum value.

Exceptions. This will produce an error, ArrayIndexOutOfBounds, when we try to get that first element. One solution is to allow this exception to be thrown, which is easiest because it requires no programming. Another would be to throw IllegalArgumentException with a more meaningful message. This would be more useful if you expected this error to occur very often, but probably isn't worth the effort. Zero-length arrays are usually produced as the result so an error earlier in the code, and they are encountered occasionally in the process of debugging.

Return index. Another way to deal with this is to change the way the method works to return the index, and when there are no elements return an impossible index (eg, -1). Many programmers won't worry about this case because it will be impossible for their program. However, you should always think about the possibility of an empty array.

Return illegal value. There is no illegal value for int, but there is for double, Double.NaN (NaN = "Not a Number"), and null can be used for object types.

Loop backwards?

Very rarely will you find a programmer who prefers to write loops that go from high to low. Of course it makes no difference in this algorithm, however, there are machines in which that can save a few nanoseconds. Backwards loops are harder to read so it's generally considered antisocial to write them without a good reason.

Collections `max` method

If you have an array of objects (not primitives), you can use the Collections.max(...) method after making the array look like a List. For example,

    String[] names = . . .;
    . . .
    String highest = Collections.max(Arrays.asList(names));

Exercises

Comparison? How would the above method perform differently if the comparison was changed from > to >= ?
Minimum. If you don't start with a value from the actual data for the initial minimum of an array of ints, what would be the best initial value to use?
Index. Write a method, indexOfMaximum, which returns the index of the maximum valued element, not the value.
Partially full. A very common situation is for arrays to be only partially full. It only takes a slight modification of the code to write a method that takes an additional parameter, size, that specifies the number of elements in the array that have values.
```
    public static int max(int[] t, int size) 
```
Strings. Rewrite the maximum method to work with the String type so that it will sort without regard to case.
( Advanced) Generic. If the elements of a class are going to be compared, the programmer of the class will have implemented the Comparable interface, which means that the class will have a compareTo(...) method. You could write the following generic method which will work for all Comparable objects.
```
    public static <T extends Comparable<T>> T max(T[] a) {
```
Often the hardest part is writing generic methods is the header, but I've written that for you. Now write the body of the method.