Find the Maximum Element in an Array

The first element is a safe starting maximum, but 0 is not

A maximum must be one of the values in a non-empty array. For [-8, -3, -11, -5], starting maximum at 0 gives the wrong result immediately: no element is greater than 0, so the stored value remains 0 even though 0 does not appear in the array. Starting maximum at a[0] gives -8, which is a real element and therefore a valid first candidate.

The sign of the values does not change this rule. Positive, zero, and negative values can all be handled by the same initialization, because the first element gives you a value from the array instead of a value chosen from outside it.

The scan starts at index 1 because index 0 is already represented

Set maximum to a[0], then compare the remaining elements at indices 1 through 3 with it. If the current element is greater, replace maximum. Otherwise, leave maximum unchanged. The array is only being read, so its values and positions do not change during the traversal.

int a[] = {-8, -3, -11, -5};
int n = 4;
int maximum = a[0];

for (int i = 1; i < n; i++) {
    if (a[i] > maximum) {
        maximum = a[i];
    }
}

int[] a = {-8, -3, -11, -5};
int n = 4;
int maximum = a[0];

for (int i = 1; i < n; i++) {
    if (a[i] > maximum) {
        maximum = a[i];
    }
}

Index 0 needs no second comparison: its value is already stored in maximum. Starting at index 1 means every remaining position is checked exactly once. For this array, -3 replaces -8, while -11 and -5 do not replace it because neither is greater than the stored candidate.

After each comparison, the candidate is the largest value seen so far

The stored value changes only when the current element is greater. It begins at -8 after visiting index 0. At index 1, -3 is greater than -8, so the candidate becomes -3. At index 2, -11 is not greater than -3, so the candidate remains -3. At index 3, -5 is also not greater than -3, so it remains -3.

This gives the scan a useful invariant: after processing an index, maximum is the largest value in the visited prefix from index 0 through that index. When a new value is greater, replacing the candidate preserves that statement. When it is not greater, keeping the candidate preserves it because the new value cannot be the largest.

When the scan ends, the candidate is the array maximum

After index 3, the visited prefix is the whole array [-8, -3, -11, -5]. The invariant therefore says that maximum is the largest value in the whole array, which is -3. No unseen value remains that could challenge the candidate.

The loop examines each remaining element once, so the running time is O(n). It stores only maximum and the loop index beyond the input array, so the extra space is O(1). This method requires n to be at least 1, because it reads a[0] before the scan begins.