Инварианты, граничные случаи и тесты

Работающий на примере код ещё не является доказательством. Инвариант объясняет, что остаётся истинным на каждом шаге, а граничные тесты проверяют места, где это утверждение легче всего нарушить.

Что требуется от максимума массива

Нужно найти максимальный элемент непустого массива за один проход. Для пустого массива договоримся сообщать ошибку: без элементов максимум не определён.

Какие лишние отношения строит перебор

Можно для каждого кандидата сравнить его со всеми остальными и выбрать тот, который не меньше каждого элемента. Это корректно, но выполняет O(n²) сравнений. Сортировка и выбор последнего элемента лучше — O(n log n), однако строит полный порядок, который задаче не нужен.

Почему полный порядок не нужен

И квадратичная проверка, и сортировка сохраняют лишнюю информацию об отношениях между всеми элементами. Для ответа достаточно одного числа — лучшего значения среди уже просмотренных.

Как расширяется максимум префикса

Если максимум префикса уже известен, после чтения нового элемента максимум увеличенного префикса равен большему из прежнего максимума и нового элемента. Значит, историю префикса хранить не нужно.

Доказываем смысл переменной best

Перед каждой итерацией best равен максимуму уже обработанного непустого префикса. Инициализация первым элементом делает утверждение истинным. Обновление best = max(best, value) сохраняет его, а после последнего шага префикс совпадает со всем массивом.

Один проход по непустому входу

1. Проверить, что массив не пуст.
2. Присвоить best значение первого элемента.
3. Для каждого следующего элемента сравнить его с best.
4. Если элемент больше, заменить best.
5. Вернуть best после прохода.

Инициализация нулём была бы ошибкой для массива из одних отрицательных чисел.

Максимум с явным контрактом пустого входа

C++17

#include <cassert>
#include <stdexcept>
#include <vector>

using namespace std;

int maximum(const vector<int>& values) {
    if (values.empty()) {
        throw invalid_argument("maximum requires a non-empty array");
    }

    int best = values.front();
    for (size_t index = 1; index < values.size(); ++index) {
        if (values[index] > best) {
            best = values[index];
        }
    }
    return best;
}

int main() {
    assert(maximum({5}) == 5);
    assert(maximum({-3, -7, -5}) == -3);
    assert(maximum({2, 9, 9, 1}) == 9);
}

Python 3

def maximum(values: list[int]) -> int:
    if not values:
        raise ValueError("maximum requires a non-empty array")

    best = values[0]
    for index in range(1, len(values)):
        if values[index] > best:
            best = values[index]
    return best


assert maximum([5]) == 5
assert maximum([-3, -7, -5]) == -3
assert maximum([2, 9, 9, 1]) == 9

Сколько сравнений действительно нужно

Алгоритм делает ровно один проход: O(n) времени и O(1) дополнительной памяти. Предполагается, что сравнение двух элементов занимает O(1). Для очень длинных строк стоимость одного сравнения зависит от длины общего префикса.

Где ломается неверная инициализация

• Пустой вход: должна сработать явно выбранная политика ошибки.
• Один элемент: он одновременно первый и максимальный.
• Все числа отрицательные: нельзя начинать с нуля.
• Максимум встречается несколько раз: значение ответа не меняется.
• Максимум находится первым или последним: проверяются обе границы прохода.

Выводим тесты из контракта и ветвей

Тесты выводятся из контракта и ветвей: [5] → 5, [-3, -7] → -3, [2, 9, 9, 1] → 9, максимум в конце [1, 2, 8] → 8, пустой массив → ошибка. Такой набор проверяет инициализацию, обновление, отсутствие обновления и политику пустого входа.

Когда короткое состояние требует инварианта

Инвариант особенно нужен, когда цикл обновляет короткое состояние: максимум префикса, сумму, границу, набор просмотренных ключей. Граничные тесты ищи около пустого входа, первого и последнего элемента, равенств и каждой ветви условия.

Когда одного максимума недостаточно

Одного максимума недостаточно, если нужны порядок элементов, позиция каждого максимума или быстрые ответы после изменений массива. Тогда состояние и структура данных должны хранить больше информации.

Три части доказательства инвариантом

Вопрос. Какие три части нужны для доказательства инвариантом?

Ответ. Инициализация показывает истинность до первого шага, сохранение — после одной итерации, завершение — почему истинный инвариант в конце даёт требуемый ответ.

Почему одного позитивного теста мало

Вопрос. Почему тест только с положительными разными числами слабый?

Ответ. Он не обнаружит ошибочную инициализацию нулём, неверную обработку равенства и обращение к отсутствующему первому элементу. Нужны отрицательные числа, дубликаты и проверка пустого входа.

Сохраняем индекс первого максимума

Расширь функцию так, чтобы она возвращала индекс первого максимума. Сначала сформулируй инвариант для пары (bestValue, bestIndex). Подсказка: обновляй пару только при строгом >, иначе более позднее равное значение вытеснит первый индекс.

Доказательство направляет тестирование

Инвариант превращает цикл в короткое доказательство, а тесты из инициализации, ветвей и границ проверяют именно те места, где доказательство может быть нарушено кодом.