Programming exercise: maximum value in integer array, part 1

This exercise is just a little bit more substantial than the last one — but not by very much. Given an array of \(n\) non-negative integers, find the maximum value in the array, or return \(-1\) if the array is empty. Obviously, the use of any built-in maximum-finding function is forbidden. While the problem is almost trivial, it does illustrate how each language works with array or vector data types, as well as how it handles iteration.

This exercise, like some of the other ones that I will also be going through, is from the book Programming Interviews Exposed by John Mongan and Noah Suojanen^[1].

For consistency, let’s assume that the array for which we’re trying to find the maximum value is \(\{6, 3, 8, 7, 1, 2, 0, 9, 4, 5\}\). Let’s also assume for simplicity that \(n\) is given, that we don’t have to check for errors (the input is a list of non-negative integers as promised), and that we can write \(-1\) for the error return code. (In production code, we would of course define a named constant such as ARRAY_EMPTY_ERROR, or use some other form of error-handling such as exceptions.)

Let’s begin with C. The code is pretty straightforward, except that I had to remind myself to declare the loop counter \(i\) outside of the loop. (Declaring it in the loop initialisation is not allowed in standards prior to C99.) It’s also a lot harder to code on paper than it is on a keyboard (my handwriting is terrible, due to atrophy). Here’s the program in C:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include<stdio.h>
 
int arraymax(int array[], int n) {
    int currentMax;
    int i;
 
    if( n<= 0) { return -1; }
 
    currentMax = array[0];
    for( i = 1; i < n; i++ ) {
        if( array[i] > currentMax ) {
            currentMax = array[i];
        }
    }
 
    return currentMax;
}
 
int main(int argc, char *argv[])
{
    int testinput[] = { 6, 3, 8, 7, 1, 2, 0, 9, 4, 5 };
    printf("max = %d\n", arraymax(testinput, 10));
}

I could, of course, have written the exact same program in C++, but to make things interesting, I’m going to use the STL vector class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include<iostream>
#include<vector>
 
using namespace std;
 
int vectormax(vector<int> vec)
{
    int currentMax;
 
    if( vec.empty() ) {
        return -1;
    }
 
    currentMax = vec[0];
    for( int i = 1; i < vec.size(); i++ ) {
        if( vec[i] > currentMax ) {
            currentMax = vec[i];
        }
    }
 
    return currentMax;
}
 
int main()
{
    int values[] = { 6, 3, 8, 7, 1, 2, 0, 9, 4, 5 };
    vector<int> testinput(values, values+10);
    cout << "max = " << vectormax(testinput) << endl;
}

The only tricky part was I had to look up how to initialise a vector without looping through the values and using push_back. The code above calls the iteration constructor, using the trick that an int array in C++ is just a pointer to its first element, and the fact that pointers are iterators.

Apparently, in the proposed c++0x standard, it will be possible to initialise a vector using a static array like this:

26
27

    // Use the initialiser list constructor.
    vector<int> testinput = { 6, 3, 8, 7, 1, 2, 0, 9, 4, 5 };

In the program above, I’ve used indices as if the vector were just a regular array. The preferred way to access vector elements in C++ is to use iterators. This means replacing lines 14–15 with the following:

14
15
16
17
18
19

    vector<int>::iterator vi = vec.begin();
    for( currentMax = *vi++; vi != vec.end(); vi++ ) {
        if( *vi > currentMax ) {
            currentMax = *vi;
        }
    }

I had to think a little bit about the loop initialisation condition, currentMax = *vi++. The iterator is dereferenced before it is incremented, which is the desired behaviour.

There are a number of differences between the C# and C/C++ programs. First, there’s the foreach statement, which makes for nicer-looking loops. Then there’s the fact that the array type specifier [] must appear before the variable name, rather than after. Here’s the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

using System;
 
public class ArrayMax {
    public static int arraymax(int[] array)
    {
        if( array.Length == 0 ) {
            return -1;
        }
 
        int currentMax = array[0];
        foreach( int value in array ) {
            if( value > currentMax ) {
                currentMax = value;
            }
        }
 
        return currentMax;
    }
 
    public static void Main() {
        int[] testinput = { 6, 3, 8, 7, 1, 2, 0, 9, 4, 5 };
        Console.WriteLine("max = {0}\n", arraymax(testinput));
    }
}

I had to remember to make the arraymax function static so that it can be called without instantiating the ArrayMax class.

The Java code is essentially identical to the C# code, mutatis mutandis:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class ArrayMax {
    public static int arraymax( int[] array ) 
    { 
        if( array.length == 0 ) {
            return -1;
        }
 
        int currentMax = array[0];
        for( int i = 1; i < array.length; i++ ) {
            if( array[i] > currentMax ) {
                currentMax = array[i];
            }
        }
 
        return currentMax;
    }
 
    public static void main( String args[]) {
        int testinput[] = { 6, 3, 8, 7, 1, 2, 0, 9, 4, 5 };
        System.out.println("max = " + arraymax(testinput) + "\n");
    }
}

Beginning in J2SE v1.5/5.0^[2], Java introduced a “for each” loop, and so lines 9–13 above should be replaced with this:

9
10
11
12
13

        for( int value : array ) {
            if( value > currentMax ) {
                currentMax = value;
            }
        }

Now that we’ve gotten the standard general-purpose imperative and object-oriented (i.e., “C-like”) languages out of the way, it’s time for some fun(ctional programming).

Of course, Lisp and Scheme already have a max function defined to get the maximum value in a list of integers, but as mentioned before, its use is forbidden to us. Nevertheless, the solution to the given problem in these languages is still very simple. How can we express the function that returns the maximum value of a list of integers? One way to do it is to express it as the folding (or reducing) of the list with a function that compares two integer values and returns the larger one. Expressed in Lisp, this function is:

1

(defun larger (x y) (if (> x y) x y))

The rest of the Lisp program easily follows:

2
3
4
5
6
7
8

(defun list-max (intlist) 
    (if (null intlist) -1
          (reduce #'larger intlist)
     ))
 
(setq intlist '( 6 3 8 7 1 2 0 9 4 5 ))
(format t "max = ~D" (list-max intlist))

(Incidentally, it’s because of things like #', which is called the sharp-quote, that some people don’t like Lisp.)

The Scheme program is essentially identical:

1
2
3
4
5
6
7
8
9
10

(define (listmax intlist) 
    (if (null? intlist) -1
          (let ( (larger (lambda (x y) (if (> x y) x y)) ) )
            (fold larger (car intlist) (cdr intlist)))
    )
)
 
(define intlist '( 6 3 8 7 1 2 0 9 4 5 ))
(display "max = ")
(display (listmax intlist))

The Python code is also very similar:

1
2
3
4
5
6
7
8

def listmax(intlist):
    if intlist == []:
        return -1
    else: 
        return reduce( lambda x, y : x if x > y else y, intlist)
 
testinput = [ 6, 3, 8, 7, 1, 2, 0, 9, 4, 5 ]
print "max =", listmax(testinput)

I really like the Python code. It combines the simplicity of the fold idea used in Lisp/Scheme with the clarity of an ALGOL-like syntax.

I should mention that another way of expressing the function that returns the maximum value in a list of integers is as a recursive function that returns the only element in a list of size one, and returns the larger of the first element and the result of the function applied to the rest of the list for a list of size two or more. However, unless the program is written using tail recursion, and one is using a compiler that optimises tail-recursive calls, the stack will grow with the size of the list, so this solution is not as good as the one using fold/reduce.

I was originally also going to write the program in the remaining languages listed in the previous post, but I’ve spent far too much time already on this exercise, and I’d like to move on to some more difficult ones. And besides, the program in the other functional languages will be very similar except for syntax, and there’s almost no point in coding a “maximum integer value in an array” function in the mathematical languages, since an optimised version of such a function is already built into them. I may return to this exercise later with additional languages, so I’ll append “part 1″ to the title of this post.

– davinci 11796

Be Sociable, Share!

•