Lesson 1 of 16

Define the Problem

Before writing code, state what the algorithm receives and what it returns. Even “find the largest number” needs rules for empty inputs and negative numbers.

Specify four things

• Input: A list of integers, allowing negatives and duplicates.
• Output: The largest integer.
• Edge case: Return None for an empty list.
• Constraint: Scan once without changing the input.

def maximum(values):
    if not values:
        return None
    best = values[0]
    for value in values:
        if value > best:
            best = value
    return best

print(maximum([-8, -2, -6]))
print(maximum([]))

This prints -2, then None. Starting the maximum at 0 fails for all-negative input. Start from a supplied value to keep a valid candidate.

Explain why it works

After each iteration, best is the largest value seen so far. This holds when it starts with the first item. Updating it whenever a larger value appears preserves the claim. After all items are inspected, it is the overall maximum.

A condition preserved through a loop is a loop invariant. Check that it holds initially, survives one iteration, and yields the intended result at termination. This gives broader evidence than passing a few examples.

Separate input handling from the algorithm

Programming exercises may read standard input. In a terminal, python3 solution.py < input.txt redirects a file into standard input. This course passes small values directly to functions so the procedure is easy to follow.

Check your understanding

What are the results for [5, 5], [-7], and []? What must you decide if the requested result changes to the position of the maximum?