1. Objectives, level and prerequisites

• Define the permitted inputs and required output of an algorithm.
• Trace a maximum search using a variable, a condition and a loop.
• Justify correctness and termination, then distinguish proof from tests.

An algorithm describes a precise method for transforming input data into a result. Here, we study deterministic algorithms that must terminate for every permitted input. A program expresses such a method in a language a machine can execute; the same method can have several programs.

By the end of this introduction, you will be able to specify the inputs and expected output, follow the values of a variable, and justify why a maximum search terminates and gives the correct result. This skill helps you check a procedure instead of trusting a plausible output.

Level: beginner. You only need to compare integers and read an ordered sequence of values, called a list here. Negative numbers are allowed. No programming language is required: begin on paper. Moving to code is an application, not a hidden prerequisite.

2. Define the problem before the method

We are looking for the greatest value in a finite, nonempty list of integers. The input may contain repetitions and does not need to be sorted. The output is a value, not its position or the number of times it appears. For [3, 7, 7, 2], the expected result is 7.

The condition “nonempty” is a precondition: it specifies the permitted inputs. The postcondition expresses the required result: the output belongs to the list and is greater than or equal to each of its values. In an empty list, there is no maximum to return. A procedure intended to accept this case as well should explicitly define an error or another result; it should not invent zero.

3. Build an unambiguous procedure

Keep a candidate named best. Initialize it with the first value, then go through the others in order. If the value being examined is strictly greater than best, replace best with that value. Otherwise, keep it. After the last value, return best.

Assignment changes a stored value: best ← x means “store the current value of x in best.” It is not an equation that remains valid forever. A condition selects the action; a loop repeats the steps for the remaining values. The order, initialization and condition are part of the method, just as much as the final result.

best ← first value of the list
for each value x after the first:
    if x > best:
        best ← x
return best

This text is pseudocode: it describes the method without imposing the syntax of a language. Do not paste it as it stands into a Python interpreter.

Illustration generated with artificial-intelligence assistance. It suggests the role of memory; the exact numerical trace and its justification are given in the text and table.

4. Follow a worked example

For [3, 7, 7, 2], initialization gives best = 3. Three values remain to be compared.

The second occurrence of 7 does not change the maximum value. The result is 7 after exactly three comparisons. With a single value, the loop does not execute and that value is returned. Counting comparisons does not measure actual execution time: the latter also depends on the program and the machine.

5. Justify correctness and termination

After each step, best is the maximum of the part already visited. This preserved property is called an invariant. It is true initially, because the visited part contains only the first value. If the next value is greater, replacing the candidate preserves the property; otherwise, keeping the candidate also preserves it. At the end, the visited part is the entire list: the postcondition is therefore satisfied.

A finite list of n values leaves n − 1 values after the first. Each step processes one of them, without going back: the number remaining decreases to zero. This justifies termination and n − 1 comparisons, even if all the values are equal. Tests on examples can reveal an error; they do not replace this justification for all permitted inputs.

6. Translate into a Python program

Here is a translation for a nonempty list of integers. values[0] refers to its first value; range(1, len(values)) goes through the indices after it. Indentation delimits the loop and the condition.

def maximum(values):
    best = values[0]
    for i in range(1, len(values)):
        x = values[i]
        if x > best:
            best = x
    return best

This function assumes that the precondition is satisfied. It is not a complete input-validation interface: an empty list causes an error when values[0] is accessed. Missing values, mixtures of types and infinite lists fall outside the defined problem. Before reusing it, specify the contract and how rejected inputs will be handled. The code is intended to help you understand the method; in practice, a built-in maximum function may be preferable.

7. Guided exercise

Trace a maximum search

For [5, 1, 9, 3], execute the procedure by hand. Build a table with the examined value, best before and best after; state the output and the number of comparisons.

Success criterion : The trace initializes best with the first value, examines each other value once and explains the decision at each comparison.

Guided solution, to consult after your attempt: the candidate starts at 5; after 1, 9 and 3, its successive values are 5, 9 and 9. Three comparisons lead to the output 9. Each row must make the examined value, the candidate before and the candidate after visible; a correct output alone is not enough to explain the reasoning.

8. Proportionate project

Specify and test a procedure

For [12, 8, 15, 15, 4], write the precondition and postcondition, trace the maximum and justify termination. Add the tests [-4, -2, -9], [6] and [3, 3]. Explain the intended handling of an empty list and why initializing to zero is dangerous.

Success criterion : The deliverable contains an explicit contract, the four traces, an invariant argument and a justification of termination. It distinguishes permitted inputs from the rejected empty case.

Work on paper first. If you then use the program, compare its output with your trace. Agreement on these few cases is a limited check; also retain the invariant argument and the justification of termination. The deliverable is a small specification accompanied by traces and tests, without collecting personal data.

9. Transfer assessment

Transfer the method to a minimum

Adapt the procedure to find the minimum of a finite, nonempty list of integers. Give the pseudocode, trace [6, -1, 4, -1] and explain the preserved property and termination. Find a counterexample to initialization to zero, then specify why an empty list remains outside the contract.

Success criterion : The method works across the entire stated domain, handles repetitions and a singleton, separates testing from proof, and justifies initialization, comparison and termination without repeating a memorized rule without explanation.

Write your justification without notes, explaining each choice. Then compare your method with the maximum search: which steps stay the same, and which decision changes?

10. Limits and common mistakes

Initializing best to zero seems to work for some lists of positive values, but fails on [-4, -2, -9]: the program then returns 0, which does not even belong to the input. Initializing with the first value avoids this hidden assumption. A singleton list and repetitions are permitted cases, not anomalies.

The maximum of a list is neither its sum nor a value that necessarily occurs only once in the list. An algorithm can be correct without being the only possible one. Another method could sort the list before choosing the last element, but this adds unnecessary work for this question alone. This unit does not prove that any arbitrary procedure terminates, or that any arbitrary program follows its method: these two properties require their own arguments.

11. Summary, active recall and next step

The approach is: define the contract, choose a method, trace a case, justify the preserved property and termination, then check the translation. A plausible output is not a general proof. Tomorrow, without rereading, revisit these four questions:

1. What distinction do you make between an algorithm and a program?
2. For [2, 5, 4], what values does the candidate take, and how many comparisons are made?
3. Why does initialization to zero fail for some inputs?
4. Explain to a beginner why the procedure terminates on every finite, nonempty list.

Short reference: the method is distinct from its translation; the trace starts at 2, becomes 5 and then stays at 5, with two comparisons. Zero incorrectly imposes a lower bound on the values. The number of elements remaining to be processed decreases by one until it reaches zero.

Proposed next step: compare searching for a value in a list with searching for its maximum. No next course has been designated yet: this root remains open to an extension of the curriculum, after qualification of the graph.

12. Sources and editorial method

This original unit brings together two independent institutional curricula: the French numérique et sciences informatiques curriculum for première, BO of 22 January 2019, appendix p. 8 “Langages et programmation” and p. 9 “Algorithmique”, and the English computing curriculum, 2013, “Key stage 2” and “Key stage 3”. Sources reread on 12 October 2026. The alignment concerns specification, sequence, selection, repetition, testing and justification; it does not certify full coverage of these curricula.

The text, examples and activities were prepared with artificial intelligence assistance. The traces and calculation cases must be checked, along with the eight language versions, before public delivery. No learning gain or human review is claimed.