1. Идея

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

Самый простой способ: просмотреть массив слева направо и хранить текущий максимум.
Каждый раз, когда встречается число больше текущего максимума, обновлять ответ.

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

• Максимум массива можно найти за один проход.
• Нет необходимости сортировать массив: сортировка была бы медленнее и вообще лишняя.
• Так как n >= 1, можно взять первый элемент как начальный максимум.
• Все остальные элементы нужно просто сравнить с ним.

Пример:

массив -5 7 3 -2 6

• сначала максимум -5
• видим 7 → новый максимум 7
• видим 3 → максимум остаётся 7
• видим -2 → максимум остаётся 7
• видим 6 → максимум остаётся 7

Ответ: 7.

3. Алгоритм

1. Считать n.
2. Считать массы коробок.
3. Присвоить mx значение первого элемента.
4. Для каждого элемента, начиная со второго:
   • если он больше mx, то обновить mx.
5. Вывести mx.

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

Будем поддерживать такой инвариант:

• после обработки первых k элементов значение mx равно максимуму среди этих k элементов.

Почему это верно:

• После чтения первого элемента mx равен ему, значит это максимум среди первого элемента.
• Пусть после обработки первых k элементов mx действительно хранит их максимум.
• Рассмотрим следующий элемент:
  • если он не больше mx, максимум не меняется;
  • если он больше mx, значит теперь именно он становится максимумом.
• Следовательно, после обработки следующего элемента инвариант сохраняется.

Когда обработаны все n элементов, mx равен максимуму всего массива, а значит это и есть ответ задачи.

5. Сложность

• Время: O(n), потому что каждый элемент рассматривается один раз.
• Память:
  • для варианта на C++: O(1), так как хранится только несколько переменных;
  • для приведённого варианта на Python: O(n), так как числа сначала сохраняются в список.

6. Код на C++17

#include <iostream>
using namespace std;

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

    long long x, mx;
    cin >> mx;
    for (int i = 1; i < n; i++) {
        cin >> x;
        if (x > mx) {
            mx = x;
        }
    }

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

7. Код на Python 3

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

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

print(mx)