Find the Maximum
The idea
Imagine judging a tallest-person contest where contestants walk past you one at a time. You remember only the tallest so far. Each new contestant is measured against your current champion; most walk on by, but occasionally one takes the title. Whoever holds it when the line ends wins.
The problem
You have a row of numbers and need the largest one. There is no shortcut: any element you never look at could have been the answer. So you scan once, left to right, carrying the index of the best value seen so far and challenging it with every new element.
Why it's slow
One pass, n-1 comparisons — and you cannot do better. If an algorithm skipped even one element, that element might have been the maximum, so the answer would be a guess. This lesson is the baseline for a whole family of interview questions: second-largest, smallest, count-above-average — all the same single-pass, carry-the-champion shape.
Pseudocode
-
assume the first element is the largest
Explain this line
Start with a working answer: position 0 is the best we have seen so far.
-
for every element after it
Explain this line
Visit every remaining element exactly once — skipping any could miss the true maximum.
-
compare it with the current champion
Explain this line
One comparison per element: challenger vs current champion.
-
if it is bigger, it becomes the champion
Explain this line
Bigger challenger takes the title; the pointer jumps to it. Ties keep the earlier champion.
-
the champion at the end is the maximum
Explain this line
No element remains unchallenged, so the survivor is provably the largest.
Complexity
| Best | Average | Worst | Space |
|---|---|---|---|
| O(n) | O(n) | O(n) | O(1) |
Exactly n-1 comparisons and one remembered index. This is the proven lower bound — a maximum cannot be found without examining every element.
Code
python
def find_max(a):
best = 0
for i in range(1, len(a)):
if a[i] > a[best]:
best = i
return a[best]java
static int findMax(int[] a) {
int best = 0;
for (int i = 1; i < a.length; i++) {
if (a[i] > a[best]) best = i;
}
return a[best];
}cpp
int findMax(const std::vector<int>& a) {
int best = 0;
for (int i = 1; i < (int)a.size(); ++i) {
if (a[i] > a[best]) best = i;
}
return a[best];
}javascript
function findMax(a) {
let best = 0;
for (let i = 1; i < a.length; i++) {
if (a[i] > a[best]) best = i;
}
return a[best];
}dart
int findMax(List<int> a) {
var best = 0;
for (var i = 1; i < a.length; i++) {
if (a[i] > a[best]) best = i;
}
return a[best];
}