CS theory problem: evaluating each element in an array only once and choosing the largest value

Question

We covered this problem in a theory class back in college.

The setup is this:

You're presented with an array of N values. You know the length of the array, but not the range of values. You are presented the elements one at a time. Each value can be examined only once, and if the value is not chosen when presented it is discarded. The goal is to choose the maximum value.

There is an algorithm that gives a better than 1/N chance of choosing the maximum, but I can't for the life of me recall what it is.

Answer 1

It's called the secretary problem.