Максимум в списке — разбор задачи

1. Идея

Нужно найти максимальную массу среди n коробок.

Самый простой и правильный способ — пройти по списку один раз и хранить ответ в переменной:

• сначала считаем, что самая тяжёлая коробка — первая;
• затем для каждой следующей коробки проверяем:
  • если её масса больше текущего максимума, обновляем максимум.

Это и есть решение за один проход, которое требуется в условии.

2. Наблюдения

Наблюдение 1

Максимум списка можно искать постепенно.

Если мы уже знаем максимум среди первых нескольких элементов, то после добавления следующего элемента новый максимум — это либо старый максимум, либо этот новый элемент.

Наблюдение 2

Нельзя начинать с 0 вместо первой массы.

В списке могут быть только отрицательные числа, например: -7 -3 -10 -3 -8

Если начать с 0, получится неправильный ответ, потому что 0 вообще может не быть в списке.

Поэтому нужно делать так:

• best = a[0]

Наблюдение 3

Достаточно одного прохода.

Не нужно сортировать массив и не нужно делать несколько циклов. Для поиска максимума хватает обычного линейного просмотра.

3. Алгоритм

1. Считать число n.
2. Считать массив a из n чисел.
3. Записать в best значение первого элемента: a[0].
4. Пройти по массиву с индекса 1 до n - 1.
5. Если a[i] > best, присвоить best = a[i].
6. После окончания цикла вывести best.

4. Почему это работает

Докажем, что после завершения алгоритма в best действительно хранится максимальный элемент массива.

Шаг 1

После инициализации best = a[0] переменная best равна максимуму среди первого элемента. Это очевидно.

Шаг 2

Пусть после обработки элементов с индексами от 0 до i - 1 переменная best хранит максимум среди них.

Теперь рассматриваем элемент a[i].

Возможны два случая:

• a[i] <= best
  Тогда максимум среди первых i + 1 элементов не меняется, и best остаётся правильным.

• a[i] > best
  Тогда новый максимум среди первых i + 1 элементов — это a[i], и мы обновляем best.

В обоих случаях после обработки элемента a[i] переменная best хранит максимум среди первых i + 1 элементов.

Шаг 3

После обработки всех элементов массива best будет максимумом среди всех n чисел.

Значит, алгоритм работает правильно.

5. Сложность

• Время: O(n), потому что массив просматривается один раз.
• Память: O(n) в данном решении, так как все числа сохраняются в массив.

6. Код на C++17

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

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

    cout << best << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

best = a[0]
for i in range(1, n):
    if a[i] > best:
        best = a[i]

print(best)