1. Идея

Нужно выбрать среди всех данных чисел такое, у которого модуль максимален, и вывести само число.

Самый прямой способ — пройти по массиву один раз и хранить текущий лучший ответ.
Если очередное число x имеет модуль больше, чем модуль текущего ответа ans, то обновляем ans = x.

В конце в ans и будет одно из чисел с максимальным модулем.

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

1. Требуется вывести не |a_i|, а само число a_i. Например, для чисел -7 и 6 ответом будет -7, потому что |-7| = 7, а |6| = 6.

2. Если несколько чисел имеют одинаковый максимальный модуль, можно вывести любое из них. Значит, при равенстве модулей ничего специально делать не нужно.

3. Достаточно сравнивать только модули:

   • если abs(x) > abs(ans), то x лучше;
   • если abs(x) <= abs(ans), то оставляем старый ответ.

4. Ограничение n <= 2 * 10^5 легко позволяет решить задачу простым линейным проходом.

3. Алгоритм

1. Считываем n.
2. Считываем все n чисел.
3. Берём первое число как начальный ответ: ans = a[0].
4. Для каждого следующего числа x:
   • если abs(x) > abs(ans), то присваиваем ans = x.
5. Выводим ans.

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

Докажем, что алгоритм действительно находит число с максимальным модулем.

После обработки первого числа ans равен единственному просмотренному числу, значит среди просмотренных чисел он корректен.

Теперь предположим, что после обработки некоторого количества чисел переменная ans хранит одно из чисел с максимальным модулем среди уже просмотренных.

Рассмотрим следующее число x.

• Если abs(x) > abs(ans), то у x модуль больше, чем у всех ранее просмотренных чисел. Тогда именно x должно стать новым ответом, и алгоритм делает ans = x.
• Если abs(x) <= abs(ans), то текущее ans остаётся одним из чисел с максимальным модулем среди всех просмотренных чисел, включая x.

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

После обработки всех чисел ans будет одним из чисел с максимальным модулем во всём массиве, что и требуется.

5. Сложность

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

6. Код на C++17

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

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

    long long ans, x;
    cin >> ans;

    for (int i = 1; i < n; i++) {
        cin >> x;
        if (llabs(x) > llabs(ans)) {
            ans = x;
        }
    }

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

7. Код на Python 3

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

ans = a[0]
for x in a[1:]:
    if abs(x) > abs(ans):
        ans = x

print(ans)